Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Wellnitz, Philip"'
Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to identify the fragments of $T$ that are at distance at most $k$ to $P$
Externí odkaz:
http://arxiv.org/abs/2410.06808
A graph property is a function $\Phi$ that maps every graph to {0, 1} and is invariant under isomorphism. In the $\#IndSub(\Phi)$ problem, given a graph $G$ and an integer $k$, the task is to count the number of $k$-vertex induced subgraphs $G'$ with
Externí odkaz:
http://arxiv.org/abs/2407.06801
The decades-old Pattern Matching with Edits problem, given a length-$n$ string $T$ (the text), a length-$m$ string $P$ (the pattern), and a positive integer $k$ (the threshold), asks to list all fragments of $T$ that are at edit distance at most $k$
Externí odkaz:
http://arxiv.org/abs/2403.18812
For the vertex selection problem $(\sigma,\rho)$-DomSet one is given two fixed sets $\sigma$ and $\rho$ of integers and the task is to decide whether we can select vertices of the input graph, such that, for every selected vertex, the number of selec
Externí odkaz:
http://arxiv.org/abs/2403.07524
We study the parameterized complexity of #IndSub($\Phi$), where given a graph $G$ and an integer $k$, the task is to count the number of induced subgraphs on $k$ vertices that satisfy the graph property $\Phi$. Focke and Roth [STOC 2022] completely c
Externí odkaz:
http://arxiv.org/abs/2311.08988
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
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 $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of
Externí odkaz:
http://arxiv.org/abs/2306.03640
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-programming algorithm computes the edit distance of two length-$n$ st
Externí odkaz:
http://arxiv.org/abs/2305.06659
Autor:
Focke, Jacob, Marx, Dániel, Inerney, Fionn Mc, Neuen, Daniel, Sankar, Govind S., Schepper, Philipp, Wellnitz, Philip
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $\sigma,\rho$ of non-negative integers, a $(\sigma,\rho)$-set of a graph $G$ is a set $S$ of vertices such that $|N(u
Externí odkaz:
http://arxiv.org/abs/2211.04278
We consider the approximate pattern matching problem under the edit distance. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to find the starting positions of all substrings of $T$ that can be transforme
Externí odkaz:
http://arxiv.org/abs/2204.03087
Given a graph property $\Phi$, we consider the problem $\mathtt{EdgeSub}(\Phi)$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge subgraph that satisfies $\Phi$. Specifical
Externí odkaz:
http://arxiv.org/abs/2011.03433