scientific article; zbMATH DE number 7053305

MaRDI QIDQ5743426zbMATH OpenFDO

Authors David Eisenstat, Claire Mathieu, Philip N. Klein

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1110.1320, https://dl.acm.org/citation.cfm?id=2095169

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Cites work

• A data structure for bicategories, with application to speeding up an approximation algorithm
• A General Approximation Technique for Constrained Forest Problems
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Fast 3-coloring triangle-free planar graphs
• 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 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 1834686 (Why is no real title available?)
• The Steiner forest problem revisited
• The Steiner problem with edge lengths 1 and 2
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(13)

• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Simultaneously load balancing for every p-norm, with reassignments
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Parameterized algorithms for Steiner forest in bounded width graphs
• Parameterized algorithms for \textsc{Steiner Forest} in bounded width graphs

This page was built for publication:

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