Show simple item record

Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent*
hal.structure.identifier
dc.contributor.authorLyra, Adria*
hal.structure.identifier
dc.contributor.authorMartinhon, Carlos A.*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553		*
dc.date.accessioned2010-06-28T12:30:12Z
dc.date.available2010-06-28T12:30:12Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4450
dc.language.isoenen
dc.subjectNP-completenessen
dc.subjectPolynomial algorithmsen
dc.subjectarc-colored tournamentsen
dc.subjectHamiltonian directed pathen
dc.subjectProperly arc-colored paths/trails and circuitsen
dc.subjectArc-colored digraphsen
dc.subject.ddc003en
dc.titleComplexity of Paths, Trails and Circuits in Arc-Colored Digraphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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].en
dc.identifier.citationpages222-233en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6108/2010
dc.relation.ispartoftitleTheory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedingsen
dc.relation.ispartofpublnameSpringer-Verlagen
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2010
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-13562-0en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-13561-3en
dc.relation.conftitle7th Annual Conference Theory and Applications of Models of Computation (TAMC)en
dc.relation.confdate2010-06
dc.relation.confcityPragueen
dc.relation.confcountryRépublique tchèqueen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-13562-0_21
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
tamc2.pdf
Size:
172.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record