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