Euclidean prize-collecting Steiner forest
From MaRDI portal
Publication:2429324
DOI10.1007/S00453-011-9491-8zbMATH Open1241.68086OpenAlexW2096477872MaRDI QIDQ2429324FDOQ2429324
Authors: Mohammad T. Hajiaghayi, MohammadHossein Bateni 
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9491-8
Recommendations
- Euclidean Prize-Collecting Steiner Forest
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- scientific article; zbMATH DE number 6783450
- Elementary approximation algorithms for prize collecting Steiner tree problems
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)
Cites Work
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The prize collecting traveling salesman problem
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A General Approximation Technique for Constrained Forest Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- A note on the prize collecting traveling salesman problem
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Title not available (Why is that?)
- Assignment problem in content distribution networks
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Prize-collecting Steiner networks via iterative rounding
- Spanning Trees—Short or Small
- The Steiner problem with edge lengths 1 and 2
- Multicommodity flow, well-linked terminals, and routing problems
- Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Dial a Ride from k-Forest
- Sparsest cuts and concurrent flows in product graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
- Title not available (Why is that?)
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- Edge-disjoint paths in planar graphs with constant congestion
- Approximating the single-sink link-installation problem in network design
- Title not available (Why is that?)
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Embedding tree metrics into low-dimensional Euclidean spaces
- Euclidean Prize-Collecting Steiner Forest
- Product Multicommodity Flow in Wireless Networks
Cited In (6)
- Euclidean Prize-Collecting Steiner Forest
- Colored Non-crossing Euclidean Steiner Forest
- Exact algorithms for budgeted prize-collecting covering subgraph problems
- Title not available (Why is that?)
- A PTAS for the geometric connected facility location problem
- A PTAS for the Steiner Forest Problem in Doubling Metrics
This page was built for publication: Euclidean prize-collecting Steiner forest
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429324)
