On Hamiltonian alternating cycles and paths
Resumen: We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.
Idioma: Inglés
DOI: 10.1016/j.comgeo.2017.05.009
Año: 2018
Publicado en: COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 68 (2018), 146-166
ISSN: 0925-7721

Factor impacto JCR: 0.343 (2018)
Categ. JCR: MATHEMATICS, APPLIED rank: 248 / 254 = 0.976 (2018) - Q4 - T3
Categ. JCR: MATHEMATICS rank: 293 / 313 = 0.936 (2018) - Q4 - T3

Factor impacto SCIMAGO: 0.492 - Computational Mathematics (Q2) - Computational Theory and Mathematics (Q2) - Geometry and Topology (Q2) - Control and Optimization (Q2) - Computer Science Applications (Q2)

Financiación: info:eu-repo/grantAgreement/ES/DGA/E58
Financiación: info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2014-60127-P
Financiación: info:eu-repo/grantAgreement/ES/MINECO-FEDER/MTM2015-63791-R
Tipo y forma: Article (PostPrint)
Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)

Creative Commons You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. You may not use the material for commercial purposes. If you remix, transform, or build upon the material, you may not distribute the modified material.


Exportado de SIDERAL (2019-11-22-14:45:27)


Este artículo se encuentra en las siguientes colecciones:
Articles



 Record created 2019-03-12, last modified 2019-11-22


Postprint:
 PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)