96 citations · 376 across the 69 of their papers we have counts for
4 papers · 2 filters
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…
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann +3
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks…
Zeros and approximations of Holant polynomials on the complex plane
Katrin Casel, Philipp Fischbeck, Tobias Friedrich +2
We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into…
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich +1
The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasona…