A PTAS for weight constrained Steiner trees in series--parallel graphs.

DOI10.1016/S0304-3975(03)00088-4zbMath1044.68123OpenAlexW2022258268MaRDI QIDQ1401399

Guangting Chen, Guoliang Xue

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00088-4

zbMATH Keywords

Steiner treesSeries-parallel graphsMultiple constraints quality of service

Mathematics Subject Classification ID

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

Related Items (3)

Risk models for the prize collecting Steiner tree problems with interval data ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner tree problem
• A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner trees, partial 2–trees, and minimum IFI networks
• Generalized steiner problem in series-parallel networks
• Networks immune to isolated failures
• Approximation Schemes for the Restricted Shortest Path Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• A simple efficient approximation scheme for the restricted shortest path problem
• Grade of service Steiner minimum trees in the Euclidean plane

This page was built for publication: A PTAS for weight constrained Steiner trees in series--parallel graphs.