A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).
Dual-Failure Distance and Connectivity Oracles
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
representative citing papers
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.
Defines rock climber and k-station distances for polygonal chains with alternating agent moves, proves equivalence to Fréchet or Hausdorff for unlimited moves, shows NP-hardness for fixed k, and gives a 2-approximation for the minimum k achieving a distance threshold.
citing papers explorer
-
Simpler and Improved Replacement Path Coverings
A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).
-
Minimum Stable Cut and Treewidth
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.
-
Rock Climber Distance: Frogs versus Dogs
Defines rock climber and k-station distances for polygonal chains with alternating agent moves, proves equivalence to Fréchet or Hausdorff for unlimited moves, shows NP-hardness for fixed k, and gives a 2-approximation for the minimum k achieving a distance threshold.