scientific article; zbMATH DE number 6381762

MaRDI QIDQ2934724zbMATH OpenFDO

Authors Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein

Publication date 18 December 2014

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cited in

(25)

• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Polynomial time approximation scheme for the rectilinear Steiner arborescence problem
• Improved Steiner tree algorithms for bounded treewidth
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• A tight lower bound for planar Steiner orientation
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• A near linear time approximation scheme for Steiner tree among obstacles in the plane
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Euclidean prize-collecting Steiner forest
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Optimal Surface Flattening
• scientific article; zbMATH DE number 5313630 (Why is no real title available?)
• scientific article; zbMATH DE number 1555959 (Why is no real title available?)
• Counting and sampling minimum cuts in genus g graphs
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• A PTAS for three-edge-connected survivable network design in planar graphs
• A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• scientific article; zbMATH DE number 7053305 (Why is no real title available?)
• A polynomial-time approximation scheme for planar multiway cut
• Global minimum cuts in surface embedded graphs
• Minimum Cuts in Surface Graphs
• Travelling on graphs with small highway dimension
• An O(n n) approximation scheme for Steiner tree in planar graphs
• Approximation schemes for planar graph connectivity problems

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 Q2934724)