Minimum node disjoint path covering for circular-arc graphs

DOI10.1016/0020-0190(79)90011-5MaRDI QIDQ1257337zbMATH OpenOpenAlexFDO

Authors Maurizio A. Bonuccelli, Daniel P. Bovet

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

Circular-ArcgraphsHamiltonian Path ProblemNode Disjoint Path CoverNp- CompleteTime Complexity

Mathematics Subject Classification ID

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

Cites work

• Algorithms on circular-arc graphs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3571501 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of computing the measure of ∪[a _i ,b _i ]

Cited in

(21)

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

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

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