\(k\)-path partitions in trees

DOI10.1016/S0166-218X(97)00012-7zbMath0890.68101MaRDI QIDQ1377668

Stephen T. Hedetniemi, Sandra M. Hedetniemi, Jing-Ho Yan, Gerard Jennhwa Chang

Publication date: 11 June 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

edge-cover problempath partition problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (18)

Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ On the \(k\)-path cover problem for cacti ⋮ Proof that pyramid networks are 1-Hamiltonian-connected with high probability ⋮ Unnamed Item ⋮ Approximation algorithms for the directed path partition problems ⋮ On the \(k\)-path partition of graphs. ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem ⋮ The path partition problem and related problems in bipartite graphs ⋮ Star Partitions of Perfect Graphs ⋮ Path partition for graphs with special blocks ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ A boundary class for the \(k\)-path partition problem ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Linear algorithm for optimal path cover problem on interval graphs
• 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
• A survey of gossiping and broadcasting in communication networks
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Hamiltonian circuits and path coverings of vertices in graphs
• On the optional hamiltonian completion problem
• The $L(2,1)$-Labeling Problem on Graphs

This page was built for publication: \(k\)-path partitions in trees