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

DOI10.1016/J.DAM.2005.07.002zbMATH Open1101.68728OpenAlexW2036803675MaRDI QIDQ2581561FDOQ2581561

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Linear-time recognition of circular-arc graphs
• An optimal path cover algorithm for cographs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Hamilton Paths in Grid Graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear algorithm for optimal path cover problem on interval graphs
• On mapping processes to processors in distributed systems
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• Stability in circular arc graphs
• Title not available (Why is that?)
• Hamiltonian circuits in interval graph generalizations
• The Hamiltonian circuit problem for circle graphs is NP-complete
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Linear time algorithms on circular-arc graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Interval graphs and maps of DNA
• Optimal covering of cacti by vertex-disjoint paths
• Paths in interval graphs and circular arc graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• An Efficient Test for Circular-Arc Graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Title not available (Why is that?)
• Deferred-query: An efficient approach for some problems 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
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Title not available (Why is that?)
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Minimum node disjoint path covering for circular-arc graphs
• Hamilton cycles in split graphs with large minimum degree
• Title not available (Why is that?)
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• The path-partition problem in bipartite distance-hereditary graphs
• The path-partition problem in block graphs
• Optimal path cover problem on block graphs
• Corrigendum to ``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
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• 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
• 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)