Presentation
The alternating path problem revisited
Author/s | Claverol Aguas, Mercè
Garijo Royo, Delia Hurtado Díaz, Ferran Lara Cuevas, María Dolores Seara Ojea, Carlos |
Editor | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Publication Date | 2013 |
Deposit Date | 2017-05-23 |
Published in |
|
Abstract | It is well known that, given n red points and n blue points on a circle, it is not always possible to find a plane geometric Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path ... It is well known that, given n red points and n blue points on a circle, it is not always possible to find a plane geometric Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path from being plane to being 1-plane, then the problem always has a solution, and even a Hamiltonian alternating cycle can be obtained on all instances. We also extend this kind of result to other configurations and provide remarks on similar problems. |
Project ID. | MTM2012-30951
DGR2009SGR1040 CRP ComPoSe EUI-EURC-2011-4306 2009/FQM-164 2010/FQM-164 |
Citation | Claverol Aguas, M., Garijo Royo, D., Hurtado Díaz, F., Lara Cuevas, M.D. y Seara Ojea, C. (2013). The alternating path problem revisited. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
The alternating path problem ... | 685.1Kb | [PDF] | View/ | |