\(k\)-path partitions in trees

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

Jing-Ho Yan, Sandra M. Hedetniemi, Stephen T. Hedetniemi, 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 problem; path partition problem

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

Related Items

NP-completeness results for some problems on subclasses of bipartite and chordal graphs, On the \(k\)-path partition of graphs., Path partition for graphs with special blocks, On the \(k\)-path cover problem for cacti, Proof that pyramid networks are 1-Hamiltonian-connected with high probability, The path partition problem and related problems in bipartite graphs

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