On the k-path cover problem for cacti

DOI10.1016/J.TCS.2006.01.023MaRDI QIDQ2369003zbMATH OpenOpenAlexFDO

Authors Zemin Jin, Xueliang Li

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.01.023

zbMATH Keywords

\(k\)-path coverEfficient algorithmSteiner cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Optimal covering of cacti by vertex-disjoint paths
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• On the vertex \(k\)-path cover
• scientific article; zbMATH DE number 4089565
• Algorithms and Computation
• Minmax subtree cover problem on cacti
• On the computational complexity of path cover problems
• On the minimum vertex k-path cover of trees
• An optimal path cover algorithm for cographs
• On the weighted \(k\)-path vertex cover problem

Cites work

• \(k\)-path partitions in trees
• An optimal path cover algorithm for cographs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3467157 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear algorithm for optimal path cover problem on interval graphs
• Minimum node disjoint path covering for circular-arc graphs
• On mapping processes to processors in distributed systems
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• Optimal chain partitions of trees
• Optimal covering of cacti by vertex-disjoint paths
• Optimal path cover problem on block graphs and bipartite permutation graphs
• The $L(2,1)$-Labeling Problem on Graphs
• The path-partition problem in block graphs

Cited in

(9)

• Optimal covering of cacti by vertex-disjoint paths
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• The Steiner cycle and path cover problem on interval graphs
• How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem
• Minmax subtree cover problem on cacti
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• Algorithms for solving problems on graphs of bounded pathwidth
• Concatenated k-path covers
• Hamiltonian laceability of bubble-sort graphs with edge faults

This page was built for publication: On the \(k\)-path cover problem for cacti

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