Ponencia
The alternating path problem revisited
Autor/es | Claverol Aguas, Mercè
Garijo Royo, Delia Hurtado Díaz, Ferran Lara Cuevas, María Dolores Seara Ojea, Carlos |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-23 |
Publicado en |
|
Resumen | 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. |
Identificador del proyecto | MTM2012-30951
DGR2009SGR1040 CRP ComPoSe EUI-EURC-2011-4306 2009/FQM-164 2010/FQM-164 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
The alternating path problem ... | 685.1Kb | [PDF] | Ver/ | |