3 citations · 5 across the 10 of their papers we have counts for
3 papers · 1 filter
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein +1
We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
Adir Morgan, Shay Solomon, Nicole Wein
We revisit the minimum dominating set problem on graphs with arboricity bounded by . Bansal and Umboh [BU17] gave an -approximation LP rounding algorithm, which also trans…