A polynomial time approximation scheme for the two-source minimum routing cost spanning trees

DOI10.1016/S0196-6774(02)00205-5zbMath1032.68123MaRDI QIDQ4805401

Bang Ye Wu

Publication date: 14 May 2003

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsundirected graph

Mathematics Subject Classification ID

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

Related Items (15)

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 ⋮ 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 ⋮ On the intercluster distance of a tree metric ⋮ Lagrangean bounds for the optimum communication spanning tree problem ⋮ New Valid Inequalities for the Optimal Communication Spanning Tree Problem ⋮ Solving the optimum communication spanning tree problem ⋮ The swap edges of a multiple-sources routing tree ⋮ Minimax flow tree problems ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm ⋮ Network design for time‐constrained delivery ⋮ 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 the two-source minimum routing cost spanning trees