A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem
The paper presents a polynomial-time approximation scheme for the metric case (edge-length satisfying the triangle inequality) of the optimum weighted source-destination communication spanning tree problem (WSDOCT). As this is mainly a theoretical result due to unpractical PTAS complexity, the authors also present an \(O(n^2\log n+mn)\) 2-approximation for the problem which improves the time complexity required by the PTAS to achieve the same 2-approximation. The WSDOCT optimization problem is formally defined as follows: Given an undirected graph \(G = (V, E)\) with non-negative lengths \(\omega(e)\) associated to the edges and non-negative weights \(\sigma(u)\) and \(\rho(u)\) of nodes \(u\in V\), the objective is to find a spanning tree \(T\) of \(G\) that minimizes: \[ \sum\limits_{u,v\in V}(\sigma(u)\rho(v)+ \rho(u)\sigma(v))d(T, u, v), \] where \(d(H, x, y)\) is the minimum distance between nodes \(x\) and \(y\) in a graph \(H\subseteq G\).
- 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
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- A note on two problems in connexion with graphs
- 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
- A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
- 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
- scientific article; zbMATH DE number 7219313 (Why is no real title available?)
- 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
- Approximation algorithms for the optimal \(p\)-source communication spanning tree
- 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
- 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
- On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
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)
