10 citations · 12 across the 6 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DM2009
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
Stephan Kreutzer, Siamak Tazari
Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that…
cs.DM2009★ 1 cited
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Glencora Borradaile, Erik D. Demaine, Siamak Tazari
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-conne…