A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
From MaRDI portal
Publication:4943844
DOI10.1137/S009753979732253XzbMath0941.68159OpenAlexW3138832177MaRDI QIDQ4943844
Kun-Mao Chao, R. Ravi, Giuseppe Lancia, Vineet Bafna, Bang Ye Wu
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s009753979732253x
Trees (05C05) Network design and communication in computer systems (68M10) Approximation algorithms (68W25)
Related Items (42)
On the minimum routing cost clustered tree problem ⋮ On the uniform edge-partition of a tree ⋮ 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 ⋮ Exact algorithms for minimum routing cost trees ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem ⋮ Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs ⋮ Models and algorithms for network reduction ⋮ On some optimization problems in molecular biology ⋮ Optimization in telecommunication networks ⋮ On the intercluster distance of a tree metric ⋮ Lagrangean bounds for the optimum communication spanning tree problem ⋮ Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Non-approximability of weighted multiple sequence alignment. ⋮ Geometric spanning trees minimizing the Wiener index ⋮ On the approximability of the minimum strictly fundamental cycle basis problem ⋮ Models of random subtrees of a graph ⋮ MAD trees and distance-hereditary graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ New Valid Inequalities for the Optimal Communication Spanning Tree Problem ⋮ Finding best swap edges minimizing the routing cost of a spanning tree ⋮ Spanning trees: A survey ⋮ On the minimum average distance spanning tree of the hypercube ⋮ Advances in metric embedding theory ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Solving the optimum communication spanning tree problem ⋮ The zoo of tree spanner problems ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ The swap edges of a multiple-sources routing tree ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ Edge-swapping algorithms for the minimum fundamental cycle basis problem ⋮ A linear-time algorithm to compute a MAD tree of an interval graph ⋮ The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm ⋮ Non-approximability of weighted multiple sequence alignment for arbitrary metrics ⋮ DISTANCE PRESERVING SUBTREES IN MINIMUM AVERAGE DISTANCE SPANNING TREES ⋮ Compact vs. exponential-size LP relaxations ⋮ A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
This page was built for publication: A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
