Optimal chain partitions of trees

DOI10.1016/0020-0190(75)90057-5MaRDI QIDQ1223159zbMATH OpenOpenAlexFDO

Authors Jayadev Misra, Robert E. Tarjan

Publication date 1975

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(75)90057-5

Mathematics Subject Classification ID

Trees (05C05) Algorithms in computer science (68W99)

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3238209 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Finding Minimum Spanning Trees
• Optimal Sequential Partitions of Graphs

Cited in

(11)

• The approximability of the weighted Hamiltonian path completion problem on a tree
• Path covering number and \(L(2,1)\)-labeling number of graphs
• A linear algorithm for the Hamiltonian completion number of a tree
• Chain partitioning as a key element for building vehicle routing problem heuristics
• \(k\)-path partitions in trees
• Linear algorithms on recursive representations of trees
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Approximations to clustering and subgraph problems on trees
• On the \(k\)-path cover problem for cacti
• Vertex partitions of \(r\)-edge-colored graphs
• On the \(k\)-path partition of graphs.

This page was built for publication: Optimal chain partitions of trees

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