Zobrazeno 1 - 10
of 425
pro vyhledávání: '"Pilipczuk, Michal"'
Autor:
Chang, Hsien-Chih, Cohen-Addad, Vincent, Conroy, Jonathan, Le, Hung, Pilipczuk, Marcin, Pilipczuk, Michał
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1+\varepsilon$ distortion of $n$-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth $O(\varepsilon^{-1}\log^{13} n
Externí odkaz:
http://arxiv.org/abs/2411.00216
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
Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and a
Externí odkaz:
http://arxiv.org/abs/2408.16733
We give an algorithm that, given graphs $G$ and $H$, tests whether $H$ is a minor of $G$ in time ${\cal O}_H(n^{1+o(1)})$; here, $n$ is the number of vertices of $G$ and the ${\cal O}_H(\cdot)$-notation hides factors that depend on $H$ and are comput
Externí odkaz:
http://arxiv.org/abs/2404.03958
Autor:
Kowalska, Katarzyna, Pilipczuk, Michał
We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segme
Externí odkaz:
http://arxiv.org/abs/2402.16466
We design a randomized data structure that, for a fully dynamic graph $G$ updated by edge insertions and deletions and integers $k, d$ fixed upon initialization, maintains the answer to the Split Completion problem: whether one can add $k$ edges to $
Externí odkaz:
http://arxiv.org/abs/2402.08816
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
We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are boun
Externí odkaz:
http://arxiv.org/abs/2311.01890
Autor:
Casares, Antonio, Pilipczuk, Marcin, Pilipczuk, Michał, Souza, Uéverton S., Thejaswini, K. S.
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning con
Externí odkaz:
http://arxiv.org/abs/2310.20433
In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathca
Externí odkaz:
http://arxiv.org/abs/2310.20325