A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem

DOI10.1016/j.dam.2016.09.031zbMath1365.05079OpenAlexW2537053653MaRDI QIDQ2357170

Santiago Valdés Ravelo, Carlos E. Ferreira

Publication date: 19 June 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.031

zbMATH Keywords

polynomial approximation schememetric problemcommunication spanning tree problem

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (1)

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

Cites Work

• Approximation algorithms for some optimum communication spanning tree problems
• Optimum Communication Spanning Trees
• The complexity of the network design problem
• Spanning Trees and Optimization Problems
• A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• PTAS’s for Some Metric p-source Communication Spanning Tree Problems
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem