The alternating path problem revisited

Creators: Claverol Aguas, Mercè; Garijo Royo, Delia; Hurtado Díaz, Ferran; Lara Cuevas, María Dolores; Seara Ojea, Carlos; Díaz Báñez, José Miguel (Coordinador); Garijo Royo, Delia (Coordinador); Márquez Pérez, Alberto (Coordinador); Urrutia Galicia, Jorge (Coordinador)

Others:: Díaz Báñez, José Miguel; Garijo Royo, Delia; Márquez Pérez, Alberto; Urrutia Galicia, Jorge

Description

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.

Abstract

Ministerio de Economía y Competitividad

Abstract

Generalitat de Catalunya

Abstract

European Science Foundation

Abstract

Ministerio de Ciencia e Innovación

Abstract

Junta de Andalucía (Consejería de Innovación, Ciencia y Empresa)

The alternating path problem revisited

Description

Abstract

Abstract

Abstract

Abstract

Abstract

Additional details