Alternating paths in edge-colored complete graphs (Q1842658)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Alternating paths in edge-colored complete graphs |
scientific article |
Statements
Alternating paths in edge-colored complete graphs (English)
0 references
4 May 1995
0 references
An alternating path in an edge-colored graph is a path in which every two adjacent edges have different colors. In this paper, an \(O(n^{2.5})\) algorithm is given for finding the maximum number of internally vertex- disjoint alternating paths between a specified pair of vertices in an edge-colored complete graph. Related problems are studied in which further restrictions on the paths and on the edge-colorings are imposed.
0 references
NP-completeness
0 references
alternating path
0 references
edge-colored graph
0 references
algorithm
0 references
complete graph
0 references
edge-colorings
0 references
0 references
