Efficient reduction for path problems on circular-arc graphs
From MaRDI portal
Publication:802884
DOI10.1007/BF01931279zbMATH Open0726.68059MaRDI QIDQ802884FDOQ802884
Authors: S. R. Arikati, C. Pandu Rangan, Glenn K. Manacher 
Publication date: 1991
Published in: BIT (Search for Journal in Brave)
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- A Polynomial Solution to the Undirected Two Paths Problem
- Finding Hamiltonian circuits in interval graphs
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Dominating sets and domatic number of circular arc graphs
- An Efficient Test for Circular-Arc Graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- A linear algorithm for the group path problem on chordal graphs
- Corrigendum to: On the complexity of testing for odd holes and induced odd paths
- Title not available (Why is that?)
- Efficient reduction for path problems on circular-arc graphs
Cited In (11)
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Title not available (Why is that?)
- Computing and counting longest paths on circular-arc graphs in polynomial time
- Even and odd pairs in comparability and in \(P_4\)-comparability graphs
- The parity path problem on some subclasses of perfect graphs
- Intersection graphs of Helly families of subtrees
- Title not available (Why is that?)
- A polynomial algorithm for the parity path problem on perfectly orientable graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Efficient reduction for path problems on circular-arc graphs
- Finding induced paths of given parity in claw-free graphs
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)
