2 citations · 4 across the 2 of their papers we have counts for
8 papers
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
We consider the approximate pattern matching problem under the edit distance. Given a text of length , a pattern of length , and a threshold , the task is to find…
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
Marc Roth, Johannes Schmitt, Philip Wellnitz
Given a graph property , we consider the problem , where the input is a pair of a graph and a positive integer , and the task is to decide whether $G…
On Near-Linear-Time Algorithms for Dense Subset Sum
Karl Bringmann, Philip Wellnitz
In the Subset Sum problem we are given a set of positive integers and a target and are asked whether some subset of sums to . Natural parameters for this problem…
Faster Minimization of Tardy Processing Time on a Single Machine
Karl Bringmann, Nick Fischer, Danny Hermelin +2
This paper is concerned with the problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental sch…
Faster Approximate Pattern Matching: A Unified Approach
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Approximate pattern matching is a natural and well-studied problem on strings: Given a text , a pattern , and a threshold , find (the starting positions of) all substrings…
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Julian Dörfler, Marc Roth, Johannes Schmitt +1
We study the problem #IndSub(P) of counting all induced subgraphs of size k in a graph G that satisfy the property P. This problem was introduced by Jerrum and Meeks and shown to b…