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

DOI10.1006/JAGM.2000.1088MaRDI QIDQ4500852zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

undirected graphpolynomial time approximation scheme

Mathematics Subject Classification ID

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

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

Cited in

(11)

• New valid inequalities for the optimal communication spanning tree problem
• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• Approximation algorithms for the shortest total path length spanning tree problem
• Light graphs with small routing cost
• An improved algorithm for the \(k\)-source maximum eccentricity spanning trees
• 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
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• Lagrangean bounds for the optimum communication spanning tree problem
• Solving the optimum communication spanning tree problem
• On the intercluster distance of a tree metric

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)