Article ID: | iaor1997983 |
Country: | Netherlands |
Volume: | 56 |
Issue: | 2/3 |
Start Page Number: | 297 |
End Page Number: | 309 |
Publication Date: | Jan 1995 |
Journal: | Discrete Applied Mathematics |
Authors: | Manoussakis Y. |
Keywords: | computational analysis, networks: path |
In an edge-colored graph, the paper says that a path is alternating if it has at least three vertices and any two adjacent edges have different colors. Deciding whether or not there exist two disjoint alternating paths between two vertices in edge-colored graphs is NP-complete. In this work, the paper studies the existence of alternating paths between vertices by restricting ourselves to the case of edge colored complete grpahs, It first solves the ‘vertex-disjoint’ version of this problem and related questions for edge-colored complete graphs. The paper next gives efficient algorithms for finding a fixed number of pairwise vertex- or edge-disjoint paths each of which has given extremities. Related problems are proposed.