Solving the path cover problem on circular-arc graphs by using an approximation algorithm
From MaRDI portal
Publication:2581561
DOI10.1016/j.dam.2005.07.002zbMath1101.68728OpenAlexW2036803675MaRDI QIDQ2581561
Publication date: 10 January 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.07.002
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items (11)
Hamiltonian laceability of bubble-sort graphs with edge faults ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ Flow shop scheduling problem with conflict graphs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Path covering number and \(L(2,1)\)-labeling number of graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear algorithm for optimal path cover problem on interval graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Interval graphs and maps of DNA
- Hamiltonian circuits in interval graph generalizations
- On mapping processes to processors in distributed systems
- Optimal covering of cacti by vertex-disjoint paths
- Linear time algorithms on circular-arc graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Paths in interval graphs and circular arc graphs
- Minimum node disjoint path covering for circular-arc graphs
- Optimal path cover problem on block graphs and bipartite permutation graphs
- The path-partition problem in bipartite distance-hereditary graphs
- The path-partition problem in block graphs
- Linear-time recognition of circular-arc graphs
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Corrigendum to ``The path-partition problem in block graphs.
- An optimal path cover algorithm for cographs
- Optimal path cover problem on block graphs
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Stability in circular arc graphs
- An Efficient Test for Circular-Arc Graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- Deferred-query: An efficient approach for some problems on interval graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Hamilton Paths in Grid Graphs
- Hamilton cycles in split graphs with large minimum degree
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
This page was built for publication: Solving the path cover problem on circular-arc graphs by using an approximation algorithm
