96 citations · 376 across the 69 of their papers we have counts for
8 papers · 2 filters
Fixed-Parameter Sensitivity Oracles
Davide Bilò, Katrin Casel, Keerti Choudhary +5
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f…
An Efficient Branch-and-Bound Solver for Hitting Set
Thomas Bläsius, Tobias Friedrich, David Stangl +1
The hitting set problem asks for a collection of sets over a universe to find a minimum subset of that intersects each of the given sets. It is NP-hard and equivalent to th…
Space-Efficient Fault-Tolerant Diameter Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
We design -edge fault-tolerant diameter oracles (-FDOs). We preprocess a given graph on vertices and edges, and a positive integer , to construct a data struct…
Algorithms for hard-constraint point processes via discretization
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann +2
We study algorithmic applications of a natural discretization for the hard-sphere model and the Widom-Rowlinson model in a region . These models are…
Strongly Hyperbolic Unit Disk Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +1
The class of Euclidean unit disk graphs is one of the most fundamental and well-studied graph classes with underlying geometry. In this paper, we identify this class as a special c…
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
Given a graph with a source vertex , the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex and edge , the length of a shortest pat…