The parity path problem on some subclasses of perfect graphs (Q1923620): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Efficient reduction for path problems on circular-arc graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A linear algorithm for the group path problem on chordal graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Topics on perfect graphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On the complexity of testing for odd holes and induced odd paths / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3328583 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On Comparability and Permutation Graphs / rank | |||
Normal rank | |||
Revision as of 14:06, 24 May 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
