29 citations · 40 across the 6 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.DS2014★ 1 cited
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…
cs.CG2014★ 29 cited
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…
cs.CG2014
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…