A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem

DOI10.1016/J.TCS.2018.11.008MaRDI QIDQ2632008zbMATH OpenOpenAlexWikidataFDO

Authors Santiago Valdés Ravelo, Carlos E. Ferreira

Publication date 17 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.11.008

zbMATH Keywords

approximation algorithmspolynomial-time approximation schememetric problemoptimum communication spanning tree problem

Mathematics Subject Classification ID

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

Recommendations

• PTAS's for some metric \(p\)-source communication spanning tree problems
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• Approximation algorithms for some optimum communication spanning tree problems

Cites work

• scientific article; zbMATH DE number 7219313 (Why is no real title available?)
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A note on two problems in connexion with graphs
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation algorithms for some optimum communication spanning tree problems
• Finding best swap edges minimizing the routing cost of a spanning tree
• Optimum Communication Spanning Trees
• PTAS's for some metric \(p\)-source communication spanning tree problems
• The complexity of the network design problem
• The swap edges of a multiple-sources routing tree

Cited in

(6)

• Approximation algorithms for the optimal \(p\)-source communication spanning tree
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
• PTAS's for some metric \(p\)-source communication spanning tree problems
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs

This page was built for publication: A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem

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