29 citations · 40 across the 7 of their papers we have counts for
7 papers
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
Karl Bringmann, Marvin Künnemann, André Nusser
The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in ne…
Greedy Routing and the Algorithmic Small-World Phenomenom
Karl Bringmann, Ralph Keusch, Johannes Lengler +2
The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However,…
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen
We study regular expression membership testing: Given a regular expression of size and a string of size , decide whether the string is in the language described by the regul…
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Karl Bringmann
Given a set of positive integers and a target value , the Subset Sum problem asks whether any subset of sums to . A textbook pseudopolynomial time algorithm by Be…
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…