Alternating paths in edge-colored complete graphs (Q1842658): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 11:45, 1 February 2024
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
