5 citations · 7 across the 3 of their papers we have counts for
4 papers
Parameterized Complexity of Weighted Multicut in Trees
Esther Galby, Dániel Marx, Philipp Schepper +2
The Edge Multicut problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if th…
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper
For the General Factor problem we are given an undirected graph and for each vertex a finite set of non-negative integers. The task is to decide if there is a…
Subcubic Certificates for CFL Reachability
Dmitry Chistikov, Rupak Majumdar, Philipp Schepper
Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of…
Fine-Grained Complexity of Regular Expression Pattern Matching and Membership
Philipp Schepper
The currently fastest algorithm for regular expression pattern matching and membership improves the classical O(nm) time algorithm by a factor of about log^{3/2}n. Instead of focus…