An O ( n log n ) approximation scheme for Steiner tree in planar graphs
From MaRDI portal
Publication:2930256
DOI10.1145/1541885.1541892zbMath1300.05294OpenAlexW2045749371MaRDI QIDQ2930256
No author found.
Publication date: 18 November 2014
Published in: (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1541885.1541892
No records found.
No records found.
Related Items (20)
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface ⋮ Unnamed Item ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Connecting face hitting sets in planar graphs ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: An O ( n log n ) approximation scheme for Steiner tree in planar graphs
