Approximation algorithms for the shortest total path length spanning tree problem
DOI10.1016/S0166-218X(00)00185-2zbMATH Open0958.05024OpenAlexW2167725364MaRDI QIDQ1582085FDOQ1582085
Authors: Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang 
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
Recommendations
- scientific article; zbMATH DE number 1303537
- A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
- A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
- scientific article; zbMATH DE number 437549
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- Algorithms on Strings, Trees and Sequences
- A robust model for finding optimal evolutionary tree
- The complexity of the network design problem
- Efficient methods for multiple sequence alignment with guaranteed error bounds
- Optimum Communication Spanning Trees
- Worst-Case Analysis of Network Design Problem Heuristics
- Approximation algorithms for multiple sequence alignment
- Exact and approximate algorithms for optimal network design
- Multiple Alignment, Communication Cost, and Graph Matching
- Title not available (Why is that?)
Cited In (24)
- An \(O(n \log n)\) time algorithm for computing the path-length distance between trees
- The zoo of tree spanner problems
- AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM
- Algorithms – ESA 2004
- Spanning trees: A survey
- Bounded-degree light approximate shortest-path trees in doubling metrics
- On the minimum routing cost clustered tree problem
- An efficient algorithm for the length-constrained heaviest path problem on a tree
- A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
- An improved algorithm for the \(k\)-source maximum eccentricity spanning trees
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Approximation algorithms for quickest spanning tree problems
- On the \(K\) shortest path trees problem
- Computational Science and Its Applications – ICCSA 2004
- Models and algorithms for network reduction
- Approximation algorithms for somek-source shortest paths spanning tree problems
- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
- Distance preserving subtrees in minimum average distance spanning trees
- On the intercluster distance of a tree metric
- Approximation algorithms for the optimal \(p\)-source communication spanning tree
- Light graphs with small routing cost
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the minimum average distance spanning tree of the hypercube
This page was built for publication: Approximation algorithms for the shortest total path length spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582085)
