The parity path problem on some subclasses of perfect graphs (Q1923620): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: Publication / rank | |||
Normal rank | |||
Revision as of 06:16, 5 March 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
