The parity path problem on some subclasses of perfect graphs (Q1923620)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The parity path problem on some subclasses of perfect graphs |
scientific article |
Statements
The parity path problem on some subclasses of perfect graphs (English)
0 references
7 April 1997
0 references
The parity path problem is the problem of finding two paths of different parity between two vertices. The problem is NP-complete on general graphs. In this paper, the authors consider the problem for comparability (i.e., transitively orientable), permutation, and cocomparability graphs. They give polynomial algorithms for these graphs by using the transitive orientability of the graphs to modify a breadth-first search.
0 references
permutation graph
0 references
parity path problem
0 references
NP-complete
0 references
comparability
0 references
cocomparability graphs
0 references
