Minimum node disjoint path covering for circular-arc graphs
From MaRDI portal
Publication:1257337
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
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
This page was built for publication: Minimum node disjoint path covering for circular-arc graphs
