The parity path problem on some subclasses of perfect graphs

DOI10.1016/0166-218X(95)00065-YMaRDI QIDQ1923620zbMATH OpenOpenAlexFDO

Authors C. R. Satyan, C. Pandu Rangan

Publication date 7 April 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

cocomparability graphscomparabilityNP-completeparity path problempermutation graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• scientific article; zbMATH DE number 3889564
• Finding an induced path of given parity in planar graphs in polynomial time
• The even-path problem for graphs and digraphs

Cites work

• A linear algorithm for the group path problem on chordal graphs
• Efficient reduction for path problems on circular-arc graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• On Comparability and Permutation Graphs
• On the complexity of testing for odd holes and induced odd paths
• Topics on perfect graphs

Cited in

(7)

• Even and odd pairs in comparability and in P₄-comparability graphs
• Path parity and perfection
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Finding induced paths of given parity in claw-free graphs
• The parity Hamiltonian cycle problem in directed graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• A linear algorithm for the group path problem on chordal graphs

This page was built for publication: The parity path problem on some subclasses of perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923620)