Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
From MaRDI portal
Publication:476424
DOI10.1007/s00453-012-9662-2zbMath1303.05183MaRDI QIDQ476424
Glencora Borradaile, Erik D. Demaine, Siamak Tazari
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1835/
05C05: Trees
05C82: Small world graphs, complex networks (graph-theoretic aspects)
05C10: Planar graphs; geometric and topological aspects of graph theory
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
05C22: Signed and weighted graphs
Related Items
A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals, Walking through waypoints, Minimum Cuts in Surface Graphs, Correlation clustering and two-edge-connected augmentation for planar graphs, Near-linear-time deterministic plane Steiner spanners for well-spaced point sets, The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Special Frequency Quadrilaterals and an Application, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Approximation schemes for NP-hard geometric optimization problems: a survey
- Graph minors. XVI: Excluding a non-planar graph
- Local tree-width, excluded minors, and approximation algorithms
- Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- A subset spanner for Planar graphs, with application to subset TSP
- Improved Steiner Tree Algorithms for Bounded Treewidth
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
- Graph minors. II. Algorithmic aspects of tree-width
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Maintenance of a minimum spanning forest in a dynamic plane graph
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Approximation algorithms for NP-complete problems on planar graphs
- Dealing with large hidden constants
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- A faster approximation algorithm for the Steiner problem in graphs
- Faster shortest-path algorithms for planar graphs
