Alternating paths in edge-colored complete graphs

Alternating paths in edge-colored complete graphs

0.00 Avg rating0 Votes
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:
Keywords: computational analysis, networks: path
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.