dc.creator | Claverol, Mercé | es |
dc.creator | García, Alfredo | es |
dc.creator | Garijo Royo, Delia | es |
dc.creator | Seara, Carlos | es |
dc.creator | Tejel, Javier | es |
dc.date.accessioned | 2020-06-19T08:45:32Z | |
dc.date.available | 2020-06-19T08:45:32Z | |
dc.date.issued | 2018 | |
dc.identifier.citation | Claverol, M., García, A., Garijo Royo, D., Seara, C. y Tejel, J. (2018). On Hamiltonian alternating cycles and paths. Computational Geometry, 68 (march 2018), 146-166. | |
dc.identifier.issn | 0925-7721 | es |
dc.identifier.uri | https://hdl.handle.net/11441/98022 | |
dc.description.abstract | 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. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad MTM2014-60127-P | es |
dc.format | application/pdf | es |
dc.format.extent | 26 | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Computational Geometry, 68 (march 2018), 146-166. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | On Hamiltonian alternating cycles and paths | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.projectID | MTM2014-60127-P | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/abs/pii/S0925772117300421 | es |
dc.identifier.doi | 10.1016/j.comgeo.2017.05.009 | es |
dc.journaltitle | Computational Geometry | es |
dc.publication.volumen | 68 | es |
dc.publication.issue | march 2018 | es |
dc.publication.initialPage | 146 | es |
dc.publication.endPage | 166 | es |
dc.identifier.sisius | 21151664 | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | es |