Zobrazeno 1 - 10
of 120
pro vyhledávání: '"Tantau, Till"'
Vertex deletion problems for graphs are studied intensely in classical and parameterized complexity theory. They ask whether we can delete at most k vertices from an input graph such that the resulting graph has a certain property. Regarding k as the
Externí odkaz:
http://arxiv.org/abs/2406.18299
By Fagin's Theorem, NP contains precisely those problems that can be described by formulas starting with an existential second-order quantifier, followed by only first-order quantifiers (ESO formulas). Subsequent research refined this result, culmina
Externí odkaz:
http://arxiv.org/abs/2310.01134
In the maximum satisfiability problem (MAX-SAT) we are given a propositional formula in conjunctive normal form and have to find an assignment that satisfies as many clauses as possible. We study the parallel parameterized complexity of various versi
Externí odkaz:
http://arxiv.org/abs/2206.01280
Autor:
Tantau, Till
The satisfaction probability Pr[$\phi$] := Pr$_{\beta:vars(\phi) \to \{0,1\}}[\beta\models \phi]$ of a propositional formula $\phi$ is the likelihood that a random assignment $\beta$ makes the formula true. We study the complexity of the problem $k$S
Externí odkaz:
http://arxiv.org/abs/2201.08895
Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time
Externí odkaz:
http://arxiv.org/abs/2101.08735
Parallel parameterized complexity theory studies how fixed-parameter tractable (fpt) problems can be solved in parallel. Previous theoretical work focused on parallel algorithms that are very fast in principle, but did not take into account that when
Externí odkaz:
http://arxiv.org/abs/1902.07660
Autor:
Bannach, Max, Tantau, Till
Color coding is an algorithmic technique used in parameterized complexity theory to detect "small" structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color
Externí odkaz:
http://arxiv.org/abs/1901.03364
Autor:
Bannach, Max, Tantau, Till
Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compu
Externí odkaz:
http://arxiv.org/abs/1807.03604
Autor:
Bannach, Max, Tantau, Till
Given a hypergraph $H = (V,E)$, what is the smallest subset $X \subseteq V$ such that $e \cap X \neq \emptyset$ holds for all $e \in E$? This problem, known as the hitting set problem, is a basic problem in parameterized complexity theory. There are
Externí odkaz:
http://arxiv.org/abs/1801.00716
Autor:
Skambath, Malte, Tantau, Till
While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a
Externí odkaz:
http://arxiv.org/abs/1608.08385