1 citations · 1 across the 3 of their papers we have counts for
5 papers
Diameter Computation on (Random) Geometric Graphs
Thomas Bläsius, Annemarie Schaub, Marcus Wilhelm
We present an algorithm that computes the diameter of random geometric graphs (RGGs) with expected average degree for constant in $\tilde{O}(n^{\frac{3}{2}(1+δ…
Structure and Independence in Hyperbolic Uniform Disk Graphs
Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak +2
We consider intersection graphs of disks of radius in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of , where v…
Partitioning the Bags of a Tree Decomposition Into Cliques
Thomas Bläsius, Maximilian Katzmann, Marcus Wilhelm
We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algor…
Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks
Thomas Bläsius, Marcus Wilhelm
A common technique to speed up shortest path queries in graphs is to use a bidirectional search, i.e., performing a forward search from the start and a backward search from the des…
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization
Lukas Behrendt, Katrin Casel, Tobias Friedrich +3
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the…