5 citations · 9 across the 8 of their papers we have counts for
6 papers · 1 filter
Low-stretch spanning trees of graphs with bounded width
Glencora Borradaile, Erin Wolf Chambers, David Eppstein +2
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph with a linear arrange…
Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs
Glencora Borradaile, Hung Le, Baigong Zheng
We present two algorithms for the minimum feedback vertex set problem in planar graphs: an PTAS using a linear kernel and balanced separator, and a heuristic algorith…
Minor-free graphs have light spanners
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
We show that every -minor-free graph has a light -spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bou…
Time-dependent shortest paths in bounded treewidth graphs
Glencora Borradaile, Morgan Shirley
We present a proof that the number of breakpoints in the arrival function between two terminals in graphs of treewidth is when the edge arrival functions are…
Light spanners for bounded treewidth graphs imply light spanners for -minor-free graphs
Glencora Borradaile, Hung Le
Grigni and Hung~\cite{GH12} conjectured that H-minor-free graphs have -spanners that are light, that is, of weight times the weight of the minimum spanning tree f…
Optimal dynamic program for r-domination problems over tree decompositions
Glencora Borradaile, Hung Le
There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong E…