A polynomial algorithm for the parity path problem on perfectly orientable graphs

DOI10.1016/0166-218X(95)00086-7zbMath0854.68069MaRDI QIDQ1917257

Srinivasa R. Arikati, Uri N. Peled

Publication date: 7 July 1996

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

zbMATH Keywords

parity path problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (6)

Path parity and perfection ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Finding induced paths of given parity in claw-free graphs ⋮ On the \(P_4\)-components of graphs ⋮ Even and odd pairs in comparability and in \(P_4\)-comparability graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Which claw-free graphs are perfectly orderable?
• 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 recognizing perfectly orderable graphs
• A note on odd/even cycles
• On the complexity of testing for odd holes and induced odd paths
• The even-path problem for graphs and digraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions

This page was built for publication: A polynomial algorithm for the parity path problem on perfectly orientable graphs