96 citations · 442 across the 64 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 1 cited
Hitting Set for hypergraphs of low VC-dimension
Karl Bringmann, László Kozma, Shay Moran +1
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized co…
cs.SI2015
Sampling Geometric Inhomogeneous Random Graphs in Linear Time
Karl Bringmann, Ralph Keusch, Johannes Lengler
Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an…
cs.CC2015★ 28 cited
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic…