A linear algorithm for the group path problem on chordal graphs

DOI10.1016/0166-218X(93)90230-LzbMath0779.68067MaRDI QIDQ686257

Srinivasa R. Arikati, Uri N. Peled

Publication date: 19 January 1994

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

zbMATH Keywords

chordal graphsparity 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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

A polynomial algorithm for the parity path problem on perfectly orientable graphs ⋮ Intersection graphs of Helly families of subtrees ⋮ The parity path problem on some subclasses of perfect graphs ⋮ Intersection graphs of proper subtrees of unicyclic graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Finding induced paths of given parity in claw-free graphs ⋮ A linear algorithm for the group path problem on chordal graphs ⋮ Even and odd pairs in comparability and in \(P_4\)-comparability graphs ⋮ Unnamed Item ⋮ Efficient reduction for path problems on circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear algorithm for the group path problem on chordal graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Decomposition by clique separators
• On the complexity of testing for odd holes and induced odd paths

This page was built for publication: A linear algorithm for the group path problem on chordal graphs