Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

DOI10.4230/LIPIcs.STACS.2009.1835zbMath1236.68010OpenAlexW2245114686MaRDI QIDQ5389975

Siamak Tazari, Glencora Borradaile, Erik D. Demaine

Publication date: 24 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_8550.html

zbMATH Keywords

Steiner treepolynomial-time approximation schemeembedded graphsubset TSPbounded-genus graphsurvivable-network design

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

Counting and sampling minimum cuts in genus \(g\) graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Randomly removing \(g\) handles at once ⋮ Unnamed Item

This page was built for publication: Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs