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

DOI10.1016/0166-218X(95)00086-7MaRDI QIDQ1917257zbMATH OpenFDO

Authors S. R. Arikati, Uri N. Peled

Publication date 7 July 1996

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

Full work available at URL https://doi.org/10.1016/0166-218X(95)00086-7

zbMATH Keywords

parity path problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3882470
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• An efficient algorithm for computing permanental polynomials of graphs
• The parity path problem on some subclasses of perfect graphs
• scientific article; zbMATH DE number 437576
• Finding an induced path of given parity in planar graphs in polynomial time
• scientific article; zbMATH DE number 140475
• scientific article; zbMATH DE number 731861
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs

Cites work

• A linear algorithm for the group path problem on chordal graphs
• A note on odd/even cycles
• Algorithmic Aspects of Vertex Elimination on Graphs
• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• Efficient reduction for path problems on circular-arc graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• On the complexity of recognizing perfectly orderable graphs
• On the complexity of testing for odd holes and induced odd paths
• The even-path problem for graphs and digraphs
• Topics on perfect graphs
• Which claw-free graphs are perfectly orderable?

Cited in

(9)

• Even and odd pairs in comparability and in P₄-comparability graphs
• Path parity and perfection
• The parity path problem on some subclasses of perfect graphs
• On the \(P_4\)-components of graphs
• Finding induced paths of given parity in claw-free graphs
• scientific article; zbMATH DE number 437576 (Why is no real title available?)
• Finding an induced path of given parity in planar graphs in polynomial time
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• The parity problem of polymatroids without double circuits

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

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