Minimum node disjoint path covering for circular-arc graphs

DOI10.1016/0020-0190(79)90011-5zbMath0405.68044OpenAlexW1963840573MaRDI QIDQ1257337

Daniel P. Bovet, Maurizio A. Bonuccelli

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90011-5

zbMATH Keywords

Time ComplexityNp- CompleteCircular-ArcgraphsHamiltonian Path ProblemNode Disjoint Path Cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Related Items (21)

On the \(k\)-path cover problem for cacti ⋮ The path-partition problem in block graphs ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ Unnamed Item ⋮ \(k\)-path partitions in trees ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ On the \(k\)-path partition of graphs. ⋮ 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 ⋮ Optimal path cover problem on block graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Vertex partitions of \(r\)-edge-colored graphs ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Path partition for graphs with special blocks ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Optimal path cover problem on block graphs and bipartite permutation graphs ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Dominating sets and domatic number of circular arc graphs ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs

Cites Work

• Algorithms on circular-arc graphs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum node disjoint path covering for circular-arc graphs