11 citations · 19 across the 15 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.CC2023★ 1 cited
Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring, Dániel Marx, Philip Wellnitz
We study the parameterized complexity of #IndSub(), where given a graph and an integer , the task is to count the number of induced subgraphs on vertices that satisfy…
cs.CC2023★ 1 cited
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
cs.DS2023
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic…