Show simple item record

dc.contributor.authorGourvès, Laurent
dc.contributor.authorLyra, Adria
dc.contributor.authorMartinhon, Carlos A.
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2013-09-12T09:51:44Z
dc.date.available2013-09-12T09:51:44Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11639
dc.language.isoenen
dc.subjectEdge-colored graphsen
dc.subjectproperly edge-colored closed trails and cyclesen
dc.subjectproperly edge-colored paths and trailsen
dc.subjectmonochromatic pathsen
dc.subject.ddc003en
dc.titleOn paths, trails and closed 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 properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph Gc, we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in Gc, we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint pec paths (resp., trails) in Gc with endpoints in S. Further, if Gc contains no pec closed trails, we show that the problem of finding a pec s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no pec cycles. We also deal with graphs Gc containing no (almost) pec cycles or closed trails through s or t. We prove that finding 2 pec s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint pec s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the pec path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one pec s-t path is NPcomplete. This result is interesting since as proved in [1], the determination of two or more vertex disjoint pec s-t paths can be done in polynomial time. Finally, if Gc is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.en
dc.relation.isversionofjnlnameDiscrete Mathematics and Theoretical Computer Science
dc.relation.isversionofjnlvol14en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages57-74en
dc.identifier.urlsitehttps://hal.inria.fr/hal-00990589
dc.relation.isversionofjnlpublisherDiscrete Mathematics and Theoretical Computer Science (DMTCS)en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


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