89 citations · 484 across the 68 of their papers we have counts for
Showing 2009 · cs.DSShow all
3 papers · 2 filters
cs.DS2009★ 3 cited
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx
We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we s…
cs.DS2009
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Dániel Marx
An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints infl…
cs.DS2009
Treewidth reduction for constrained separation and bipartization problems
Dániel Marx, Barry O'Sullivan, Igor Razgon
We present a method for reducing the treewidth of a graph while preserving all the minimal separators. This technique turns out to be very useful for establishing the fixed-p…