Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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+δ…
cs.DS2019
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…