Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs

DOI10.1007/s00453-012-9662-2zbMath1303.05183OpenAlexW1607394607MaRDI 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/

zbMATH Keywords

Steiner treepolynomial-time approximation schemebounded-genus graphssubset TSP

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Signed and weighted graphs (05C22)

Related Items (9)

Minimum Cuts in Surface Graphs ⋮ A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Special Frequency Quadrilaterals and an Application ⋮ Walking through waypoints ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs