The parity path problem on some subclasses of perfect graphs

DOI10.1016/0166-218X(95)00065-YzbMath0859.05056OpenAlexW1970625924MaRDI QIDQ1923620

C. Pandu Rangan, C. R. Satyan

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

comparabilityNP-completecocomparability graphspermutation graphparity path problem

Mathematics Subject Classification ID

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

Related Items (3)

Finding induced paths of given parity in claw-free graphs ⋮ Even and odd pairs in comparability and in \(P_4\)-comparability graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• A linear algorithm for the group path problem on chordal graphs
• Topics on perfect graphs
• Efficient reduction for path problems on circular-arc graphs
• On the complexity of testing for odd holes and induced odd paths
• On Comparability and Permutation Graphs

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