96 citations · 442 across the 64 of their papers we have counts for
4 papers · 1 filter
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds
Karl Bringmann, Marvin Künnemann
The Fréchet distance is a well-studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown…
Parameterized Complexity Dichotomy for Steiner Multicut
Karl Bringmann, Danny Hermelin, Matthias Mnich +1
The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt V(G) of size at most p, and an integer k, whether there is a set S of at most k…
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Karl Bringmann
The Frechet distance is a well-studied and very popular measure of similarity of two curves. Many variants and extensions have been studied since Alt and Godau introduced this meas…
Counting Triangulations and other Crossing-Free Structures Approximately
Victor Alvarez, Karl Bringmann, Saurabh Ray +1
We consider the problem of counting straight-edge triangulations of a given set of points in the plane. Until very recently it was not known whether the exact number of tri…