A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

DOI10.1006/JAGM.2000.1088zbMATH Open0958.68131OpenAlexW2076522498MaRDI QIDQ4500852FDOQ4500852

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

Publication date: 27 August 2000

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

Full work available at URL: https://doi.org/10.1006/jagm.2000.1088

Recommendations

• Approximation algorithms for some optimum communication spanning tree problems
• scientific article; zbMATH DE number 1303537
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees

zbMATH Keywords

undirected graphpolynomial time approximation scheme

Mathematics Subject Classification ID

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

Cited In (11)

• Solving the optimum communication spanning tree problem
• New valid inequalities for the optimal communication spanning tree problem
• An improved algorithm for the \(k\)-source maximum eccentricity spanning trees
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem
• Approximation algorithms for the shortest total path length spanning tree problem
• Lagrangean bounds for the optimum communication spanning tree problem
• On the intercluster distance of a tree metric
• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• Light graphs with small routing cost

This page was built for publication: A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

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