The parity path problem on some subclasses of perfect graphs (Q1923620): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1970625924 / rank | |||
Normal rank | |||
Latest revision as of 12:00, 30 July 2024
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
