Solving the path cover problem on circular-arc graphs by using an approximation algorithm

DOI10.1016/J.DAM.2005.07.002MaRDI QIDQ2581561zbMATH OpenOpenAlexFDO

Authors Ruo-Wei Hung, Maw-Shang Chang

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

zbMATH Keywords

Hamiltonian cycleHamiltonian pathGraph algorithmsInterval graphsCircular-arc graphsPath cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Paths in interval graphs and circular arc graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• On the \(k\)-path cover problem for cacti
• Efficient reduction for path problems on circular-arc graphs
• Linear algorithm for optimal path cover problem on interval graphs

Cites work

• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1308950 (Why is no real title available?)
• scientific article; zbMATH DE number 2089962 (Why is no real title available?)
• scientific article; zbMATH DE number 842876 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• An Efficient Test for Circular-Arc Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• An optimal path cover algorithm for cographs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Corrigendum to ``The path-partition problem in block 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
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Hamilton Paths in Grid Graphs
• Hamilton cycles in split graphs with large minimum degree
• Hamiltonian circuits in interval graph generalizations
• Interval graphs and maps of DNA
• Linear algorithm for optimal path cover problem on interval graphs
• Linear time algorithms on circular-arc graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Linear-time recognition of circular-arc graphs
• Minimum node disjoint path covering for circular-arc graphs
• On mapping processes to processors in distributed systems
• Optimal covering of cacti by vertex-disjoint paths
• Optimal path cover problem on block graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Paths in interval graphs and circular arc graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Stability in circular arc graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The path-partition problem in bipartite distance-hereditary graphs
• The path-partition problem in block graphs

Cited in

(12)

• Path covering number and \(L(2,1)\)-labeling number of graphs
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• Flow shop scheduling problem with conflict graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Hamiltonian laceability of bubble-sort graphs with edge faults
• Efficient reduction for path problems on circular-arc graphs
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor

This page was built for publication: Solving the path cover problem on circular-arc graphs by using an approximation algorithm

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