Alternating paths in edge-colored complete graphs (Q1842658): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 04:53, 5 March 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
