@inproceedings{407f9ddc43684db58a4f36cbb4ec9abd,
title = "Paths and trails in edge-colored graphs",
abstract = "This paper deals with the existence and search of Properly Edge-Colored paths/trails between two, not necessarily distinct, vertices s and t in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s∈-∈t path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest Properly Edge-Colored path/trail between s and t for some particular graphs and characterize edge-colored graphs without Properly Edge-Colored closed trails. Next, we prove that deciding whether there exist k pairwise vertex/edge disjoint Properly Edge-Colored s∈-∈t paths/trails in a c-edge-colored graph G c is NP-complete even for k∈=∈2 and c∈=∈Ω(n 2), where n denotes the number of vertices in G c . Moreover, we prove that these problems remain NP-complete for c-colored graphs containing no Properly Edge-Colored cycles and c∈=∈Ω(n). We obtain some approximation results for those maximization problems together with polynomial results for some particulars classes of edge-colored graphs.",
keywords = "Connectivity, Edge colored graphs, Properly edge-colored paths, Trails and cycles",
author = "A. Abouelaoualim and Das, \{K. Ch\} and L. Faria and Y. Manoussakis and C. Martinhon and R. Saad",
year = "2008",
doi = "10.1007/978-3-540-78773-0\_62",
language = "English",
isbn = "3540787720",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "723--735",
booktitle = "LATIN 2008",
note = "8th Latin American TheoreticalINformatics Symposium, LATIN 2008 ; Conference date: 07-04-2008 Through 11-04-2008",
}