Show simple item record

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.identifierUniversidade Federal Rural do Rio de Janeiro [UFRRJ]
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.accessioned2013-06-24T07:25:46Z
dc.date.available2013-06-24T07:25:46Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11469
dc.language.isoenen
dc.subjectProperly arc-colored paths/trails and circuitsen
dc.subjectArc-colored digraphsen
dc.subjectHamiltonian directed pathen
dc.subjectArc-colored tournamentsen
dc.subjectPolynomial algorithmsen
dc.subjectNP-completenessen
dc.subject.ddc003en
dc.titleComplexity of trails, paths and circuits in arc-colored digraphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe deal with different algorithmic questions regarding properly arc-colored s–ts–t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph DcDc with c≥2c≥2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s–ts–t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s–ts–t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c=Ω(n)c=Ω(n), where nn denotes the number of vertices in DcDc. 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 xx (resp., properly arc-colored Hamiltonian s–ts–t path) is NP-complete for c≥2c≥2. As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a 22-arc-colored tournament contains a properly arc-colored circuit.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol161en
dc.relation.isversionofjnlissue6en
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages819-828en
dc.relation.isversionofdoi10.1016/j.dam.2012.10.025en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01508740*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record