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

DOI10.1007/S00453-012-9662-2MaRDI QIDQ476424zbMATH OpenOpenAlexFDO

Authors 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

bounded-genus graphspolynomial-time approximation schemeSteiner treesubset TSP

Mathematics Subject Classification ID

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

Recommendations

• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Approximating connectivity domination in weighted bounded-genus graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• scientific article; zbMATH DE number 6381654

Cites work

• A faster approximation algorithm for the Steiner problem in graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• A subset spanner for Planar graphs, with application to subset TSP
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Bidimensionality: new connections between FPT algorithms and PTASs
• Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Faster shortest-path algorithms for planar graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XVI: Excluding a non-planar graph
• Graphs on surfaces
• Greedy optimal homotopy and homology generators
• scientific article; zbMATH DE number 6381654 (Why is no real title available?)
• scientific article; zbMATH DE number 6381762 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• Improved Steiner tree algorithms for bounded treewidth
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Local tree-width, excluded minors, and approximation algorithms
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Multiple source shortest paths in a genus g graph
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The Two-Edge Connectivity Survivable Network Problem in Planar Graphs

Cited in

(16)

• Approximation algorithms via contraction decomposition
• 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
• A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
• Approximating connectivity domination in weighted bounded-genus graphs
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Minimum Cuts in Surface Graphs
• Walking through waypoints
• Correlation clustering and two-edge-connected augmentation for planar graphs
• The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
• Exploration of graphs with excluded minors
• Approximation schemes for planar graph connectivity problems
• Faster diameter computation in graphs of bounded Euler genus
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476424)