Zobrazeno 1 - 10
of 151
pro vyhledávání: '"SOKOŁOWSKI MAREK"'
Autor:
Chekan, Vera, Geniet, Colin, Hatzel, Meike, Pilipczuk, Michał, Sokołowski, Marek, Seweryn, Michał T., Witkowski, Marcin
For a group $\Gamma$, a $\Gamma$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $\Gamma$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null i
Externí odkaz:
http://arxiv.org/abs/2408.16344
Autor:
Korhonen, Tuukka, Sokołowski, Marek
We give an algorithm that given a graph $G$ with $n$ vertices and $m$ edges and an integer $k$, in time $O_k(n^{1+o(1)}) + O(m)$ either outputs a rank decomposition of $G$ of width at most $k$ or determines that the rankwidth of $G$ is larger than $k
Externí odkaz:
http://arxiv.org/abs/2402.12364
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is no
Externí odkaz:
http://arxiv.org/abs/2401.16230
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all the performed operations on reals (typically comparisons and additions)
Externí odkaz:
http://arxiv.org/abs/2311.03321
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings thr
Externí odkaz:
http://arxiv.org/abs/2310.20623
Autor:
Bergougnoux, Benjamin, Gajarský, Jakub, Guśpiel, Grzegorz, Hliněný, Petr, Pokrývka, Filip, Sokołowski, Marek
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomass\'e and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited
Externí odkaz:
http://arxiv.org/abs/2307.01732
Let $d$ be a positive integer. For a finite set $X \subseteq \mathbb{R}^d$, we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} \lambda_x \cdot x \mid \lambda_x \in \mathbb{Z}_{\geq 0} \} \subseteq \mathbb{R}^d$. Goemans a
Externí odkaz:
http://arxiv.org/abs/2307.00406
We present a data structure that for a dynamic graph $G$ that is updated by edge insertions and deletions, maintains a tree decomposition of $G$ of width at most $6k+5$ under the promise that the treewidth of $G$ never grows above $k$. The amortized
Externí odkaz:
http://arxiv.org/abs/2304.01744
Autor:
Gajarský, Jakub, Mählmann, Nikolas, McCarty, Rose, Ohlmann, Pierre, Pilipczuk, Michał, Przybyszewski, Wojciech, Siebertz, Sebastian, Sokołowski, Marek, Toruńczyk, Szymon
A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known
Externí odkaz:
http://arxiv.org/abs/2301.13735
In the directed detour problem one is given a digraph $G$ and a pair of vertices $s$ and~$t$, and the task is to decide whether there is a directed simple path from $s$ to $t$ in $G$ whose length is larger than $\mathsf{dist}_{G}(s,t)$. The more gene
Externí odkaz:
http://arxiv.org/abs/2301.02421