On the k-path cover problem for cacti
DOI10.1016/J.TCS.2006.01.023zbMATH Open1088.68142OpenAlexW2054418670MaRDI QIDQ2369003FDOQ2369003
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)
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
- An optimal path cover algorithm for cographs
- Linear algorithm for optimal path cover problem on interval graphs
- On mapping processes to processors in distributed systems
- Title not available (Why is that?)
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- The $L(2,1)$-Labeling Problem on Graphs
- Optimal covering of cacti by vertex-disjoint paths
- Minimum node disjoint path covering for circular-arc graphs
- Optimal chain partitions of trees
- The path-partition problem in block graphs
- On the \(k\)-path partition of graphs.
- \(k\)-path partitions in trees
- On the \(k\)-path partition problem in cographs
Cited In (8)
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem
- Concatenated \(k\)-path covers
- Minmax subtree cover problem on cacti
- The Steiner cycle and path cover problem on interval graphs
- Hamiltonian laceability of bubble-sort graphs with edge faults
- Algorithms for solving problems on graphs of bounded pathwidth
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)
