On the \(k\)-path cover problem for cacti

DOI10.1016/j.tcs.2006.01.023zbMath1088.68142OpenAlexW2054418670MaRDI QIDQ2369003

Xue Liang Li, Ze-min Jin

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

Efficient algorithm\(k\)-path coverSteiner cover

Mathematics Subject Classification ID

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

Related Items (3)

Unnamed Item ⋮ Hamiltonian laceability of bubble-sort graphs with edge faults ⋮ Efficient algorithm for the vertex cover \(P_k\) problem on cacti

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithm for optimal path cover problem on interval graphs
• On mapping processes to processors in distributed systems
• Optimal covering of cacti by vertex-disjoint paths
• Optimal chain partitions of trees
• Minimum node disjoint path covering for 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.
• An optimal path cover algorithm for cographs
• Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
• The $L(2,1)$-Labeling Problem on Graphs

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