Alternating paths in edge-colored complete graphs (Q1842658)

From MaRDI portal
Revision as of 10:45, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references