Efficient reduction for path problems on circular-arc graphs

DOI10.1007/BF01931279zbMath0726.68059MaRDI QIDQ802884

Srinivasa R. Arikati, Glenn K. Manacher, C. Pandu Rangan

Publication date: 1991

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

interval graphsparity path problemtwo path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

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 ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Finding induced paths of given parity in claw-free 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
• Efficient reduction for path problems on circular-arc graphs
• Finding Hamiltonian circuits in interval graphs
• Dominating sets and domatic number of circular arc graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• An Efficient Test for Circular-Arc Graphs
• A Polynomial Solution to the Undirected Two Paths Problem

This page was built for publication: Efficient reduction for path problems on circular-arc graphs