Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
From MaRDI portal
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
- Title not available (Why is no real title available?)
- 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?)
- 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 faster approximation algorithm for the Steiner problem in graphs
- A subset spanner for Planar graphs, with application to subset TSP
- 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
- 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
(13)- Special frequency quadrilaterals and an application
- A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Approximating connectivity domination in weighted bounded-genus graphs
- The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
- Approximation algorithms via contraction decomposition
- 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
- Walking through waypoints
- The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem
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)
