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

DOI10.1016/J.TCS.2018.11.008zbMATH Open1426.68307OpenAlexW2901018354WikidataQ128930595 ScholiaQ128930595MaRDI QIDQ2632008FDOQ2632008

Carlos E. Ferreira, Santiago Valdés Ravelo

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

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

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)

Cites Work

• A note on two problems in connexion with graphs
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• The complexity of the network design problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation algorithms for some optimum communication spanning tree problems
• Optimum Communication Spanning Trees
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• The swap edges of a multiple-sources routing tree
• Finding best swap edges minimizing the routing cost of a spanning tree
• 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
• Title not available (Why is that?)
• A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
• PTAS’s for Some Metric p-source Communication Spanning Tree Problems

Cited In (3)

• 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
• Approximation algorithms for the optimal \(p\)-source communication spanning tree

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)