Approximation algorithms for the shortest total path length spanning tree problem

DOI10.1016/S0166-218X(00)00185-2zbMath0958.05024OpenAlexW2167725364MaRDI QIDQ1582085

Kun-Mao Chao, Chuan Yi Tang, Bang Ye Wu

Publication date: 27 February 2001

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00185-2

zbMATH Keywords

approximation algorithmspanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

On the minimum routing cost clustered tree problem ⋮ Approximation algorithms for the optimal \(p\)-source communication spanning tree ⋮ An improved algorithm for the \(k\)-source maximum eccentricity spanning trees ⋮ Light graphs with small routing cost ⋮ Models and algorithms for network reduction ⋮ On the intercluster distance of a tree metric ⋮ Spanning trees: A survey ⋮ On the minimum average distance spanning tree of the hypercube ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ The zoo of tree spanner problems ⋮ AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM ⋮ DISTANCE PRESERVING SUBTREES IN MINIMUM AVERAGE DISTANCE SPANNING TREES

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment
• A robust model for finding optimal evolutionary tree
• Optimum Communication Spanning Trees
• Worst-Case Analysis of Network Design Problem Heuristics
• Multiple Alignment, Communication Cost, and Graph Matching
• The complexity of the network design problem
• Exact and approximate algorithms for optimal network design
• Algorithms on Strings, Trees and Sequences

This page was built for publication: Approximation algorithms for the shortest total path length spanning tree problem