Zobrazeno 1 - 10
of 265
pro vyhledávání: '"Kratsch, Stefan"'
Autor:
Kratsch, Stefan, Le, Van Bang
A stable cutset in a graph $G$ is a set $S\subseteq V(G)$ such that vertices of $S$ are pairwise non-adjacent and such that $G-S$ is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is
Externí odkaz:
http://arxiv.org/abs/2407.02086
Autor:
Bojikian, Narek, Kratsch, Stefan
Recently, Bojikian and Kratsch [2023] have presented a novel approach to tackle connectivity problems parameterized by clique-width ($\operatorname{cw}$), based on counting small representations of partial solutions (modulo two). Using this technique
Externí odkaz:
http://arxiv.org/abs/2402.08046
Autor:
Bojikian, Narek, Kratsch, Stefan
Recently, Hegerfeld and Kratsch [ESA 2023] obtained the first tight algorithmic results for hard connectivity problems parameterized by clique-width. Concretely, they gave one-sided error Monte-Carlo algorithms that given a $k$-clique-expression solv
Externí odkaz:
http://arxiv.org/abs/2307.14264
Autor:
Chekan, Vera, Kratsch, Stefan
In this work, we study two natural generalizations of clique-width introduced by Martin F\"urer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while for fusion-width (fw) we have a possibility to merge all vertices
Externí odkaz:
http://arxiv.org/abs/2307.04628
Autor:
Kratsch, Stefan, Kunz, Pascal
An $\alpha$-approximate polynomial Turing kernelization is a polynomial-time algorithm that computes an $(\alpha c)$-approximate solution for a parameterized optimization problem when given access to an oracle that can compute $c$-approximate solutio
Externí odkaz:
http://arxiv.org/abs/2307.02241
Autor:
Hegerfeld, Falko, Kratsch, Stefan
We study connectivity problems from a fine-grained parameterized perspective. Cygan et al. (TALG 2022) obtained algorithms with single-exponential running time $\alpha^{tw} n^{O(1)}$ for connectivity problems parameterized by treewidth ($tw$) by intr
Externí odkaz:
http://arxiv.org/abs/2302.14128
Autor:
Hegerfeld, Falko, Kratsch, Stefan
The complexity of problems involving global constraints is usually much more difficult to understand than the complexity of problems only involving local constraints. A natural form of global constraints are connectivity constraints. We study connect
Externí odkaz:
http://arxiv.org/abs/2302.03627
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van Geffen et al. posed this question for odd cycle transversal and feedbac
Externí odkaz:
http://arxiv.org/abs/2212.12385
Autor:
Kratsch, Stefan, Nelles, Florian
Many computational problems admit fast algorithms on special inputs, however, the required properties might be quite restrictive. E.g., many graph problems can be solved much faster on interval or cographs, or on graphs of small modular-width or smal
Externí odkaz:
http://arxiv.org/abs/2209.14429
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\Gamma$, with or without weights. More precisely, for each finite Boolean constraint language $\Gamma
Externí odkaz:
http://arxiv.org/abs/2207.07422