Efficient reduction for path problems on circular-arc graphs

DOI10.1007/BF01931279MaRDI QIDQ802884zbMATH OpenFDO

Authors S. R. Arikati, C. Pandu Rangan, Glenn K. Manacher

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)

Recommendations

• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• On the approximability of path and cycle problems in arc-dependent networks
• scientific article; zbMATH DE number 140475
• Linear time algorithms on circular-arc graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Efficient and perfect domination on circular-arc graphs
• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• scientific article; zbMATH DE number 4215389

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4117882 (Why is no real title available?)
• A Polynomial Solution to the Undirected Two Paths Problem
• A linear algorithm for the group path problem on chordal graphs
• An Efficient Test for Circular-Arc Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Dominating sets and domatic number of circular arc graphs
• Efficient reduction for path problems on circular-arc graphs
• Finding Hamiltonian circuits in interval graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs

Cited in

(11)

• The parity path problem on some subclasses of perfect graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• scientific article; zbMATH DE number 140475 (Why is no real title available?)
• Finding induced paths of given parity in claw-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Efficient reduction for path problems on circular-arc graphs
• Intersection graphs of Helly families of subtrees
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Even and odd pairs in comparability and in \(P_4\)-comparability graphs
• Large Induced Subgraphs via Triangulations and CMSO

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

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