Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
From MaRDI portal
Publication:5395666
DOI10.1145/2027216.2027219zbMath1281.68233OpenAlexW2570206580MaRDI QIDQ5395666
Dániel Marx, MohammadHossein Bateni, Mohammad Taghi Hajiaghayi
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2027216.2027219
dynamic programmingapproximation algorithmplanar graphnetwork designseries-parallel graphPTASSteiner forestbounded-treewidth
Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Quasilinear approximation scheme for Steiner multi cycle in the Euclidean plane, Hitting Weighted Even Cycles in Planar Graphs, A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, Correlation clustering and two-edge-connected augmentation for planar graphs, Approximation algorithms for Steiner forest: An experimental study, Randomized approximation scheme for Steiner multi cycle in the Euclidean plane, On the complexity of the regenerator location problem treewidth and other parameters, Fission: Practical algorithms for computing minimum balanced node separators, Unnamed Item, Euclidean prize-collecting Steiner forest, A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem, A PTAS for the Steiner Forest Problem in Doubling Metrics, Stronger MIP formulations for the Steiner forest problem, An Efficient Approximation Algorithm for the Steiner Tree Problem, A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, An improved algorithm for the Steiner tree problem with bounded edge-length, An Exact Algorithm for the Steiner Forest Problem, On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Travelling on graphs with small highway dimension, Efficient Black-Box Reductions for Separable Cost Sharing, Placing Green bridges optimally, with a multivariate analysis
