Published May 23, 2017 | Version v1
Publication Metadata-only

The alternating path problem revisited

Creators

Contributors

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)

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/60281
URN
urn:oai:idus.us.es:11441/60281

Origin repository

Origin repository
USE