Show simple item record

dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMartinhon, Carlos A.*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorAdria, Lyra*
dc.contributor.authorProtti, Fabio*
dc.date.accessioned2010-03-17T13:44:47Z
dc.date.available2010-03-17T13:44:47Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3726
dc.language.isoenen
dc.subjectmonochromatic pathsen
dc.subjectproperly edge-colored paths/trailsen
dc.subjectEdge-colored graphsen
dc.subject.ddc003en
dc.titleOn s-t paths and trails in edge-colored graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper we deal from an algorithmic perspective with different questions regarding monochromatic and properly edge-colored s-t paths/trails on edge-colored graphs. Given a c-edge-colored graph Gc without properly edge-colored closed trails, we present a polynomial time procedure for the determination of properly edge-colored s-t trails visiting all vertices of Gc a prescribed number of times. As an immediate consequence, we polynomially solve the Hamiltonian path (resp., Eulerian trail) problem for this particular class of graphs. In addition, we prove that to check whether Gc contains 2 properly edge-colored s-t paths/trails with length at most L>0 is NP-complete in the strong sense. Finally, we prove that, if Gc is a general c-edge-colored graph, to find 2 monochromatic vertex disjoint s-t paths with different colors is NP-complete.en
dc.relation.isversionofjnlnameElectronic Notes in Discrete Mathematics
dc.relation.isversionofjnlvol35en
dc.relation.isversionofjnldate2009-12
dc.relation.isversionofjnlpages221-226en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.endm.2009.11.037en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
hal.person.labIds989*
hal.person.labIds*
hal.person.labIds989*
hal.person.labIds*
hal.person.labIds*


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