A polynomial algorithm for the parity path problem on perfectly orientable graphs
From MaRDI portal
Publication:1917257
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)
Related Items
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
- 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
- Unnamed Item