A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2O(n1−1/d) for any fixed dimension d≥ 2 for …