
Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010), Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs, Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings, Springer-Verlag : Berlin, p. 222-233. http://dx.doi.org/10.1007/978-3-642-13562-0_21
View/ Open
Type
Communication / ConférenceDate
2010Conference title
7th Annual Conference Theory and Applications of Models of Computation (TAMC)Conference date
2010-06Conference city
PragueConference country
République tchèqueBook title
Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. ProceedingsPublisher
Springer-Verlag
Series title
Lecture Notes in Computer ScienceSeries number
6108/2010Published in
Berlin
ISBN
978-3-642-13561-3
Pages
222-233
Publication identifier
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lyra, Adria
Martinhon, Carlos A.
Monnot, Jérôme

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We deal with different algorithmic questions regarding properly arc-colored s-t paths, trails and circuits in arc-colored digraphs. Given an arc-colored digraph D c with c ≥ 2 colors, we show that the problem of maximizing the number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time. Surprisingly, we prove that the determination of one properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c = Ω(n), where n denotes the number of vertices in D c . If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex x (resp., properly arc-colored Hamiltonian s-t path) is NP-complete, even if c = 2. As a consequence, we solve a weak version of an open problem posed in Gutin et. al. [17].Subjects / Keywords
NP-completeness; Polynomial algorithms; arc-colored tournaments; Hamiltonian directed path; Properly arc-colored paths/trails and circuits; Arc-colored digraphsRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2013) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2012) Article accepté pour publication ou publié
-
Gourvès, Laurent; Martinhon, Carlos A.; Monnot, Jérôme; Adria, Lyra; Protti, Fabio (2009) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2010) Article accepté pour publication ou publié
-
Gourvès, Laurent; Lyra, Adria; Martinhon, Carlos A.; Monnot, Jérôme (2009) Communication / Conférence