Zobrazeno 1 - 10
of 33
pro vyhledávání: '"Nadara, Wojciech"'
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
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
The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$: a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bound by the ancestor/descendant relation. We propose an algorithm that g
Externí odkaz:
http://arxiv.org/abs/2205.02656
In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output
Externí odkaz:
http://arxiv.org/abs/2105.01699
Publikováno v:
ACM Transactions on Algorithms, 19/2:1--19, 2023
We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our
Externí odkaz:
http://arxiv.org/abs/2008.00779
Autor:
Chen, Jiehua, Czerwiński, Wojciech, Disser, Yann, Feldmann, Andreas Emil, Hermelin, Danny, Nadara, Wojciech, Pilipczuk, Michał, Pilipczuk, Marcin, Sorge, Manuel, Wróblewski, Bartłomiej, Zych-Pawlewicz, Anna
We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{{\cal O
Externí odkaz:
http://arxiv.org/abs/2006.00571
We study the Many Visits TSP problem, where given a number $k(v)$ for each of $n$ cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city $v$ exactly $k(v)$ times. The currently fastest algor
Externí odkaz:
http://arxiv.org/abs/2005.02329
Autor:
Bonamy, Marthe, Dross, François, Masařík, Tomáš, Nadara, Wojciech, Pilipczuk, Marcin, Pilipczuk, Michał
Publikováno v:
The Electronic Journal of Combinatorics 28(4), 5:1-5:12, 2021
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain $k+1$ vertex-disjoint cycles, then it suffices to delete $2k$ vertices to obtain a forest.
Externí odkaz:
http://arxiv.org/abs/1912.01570
Autor:
Nadara, Wojciech, Smulewicz, Marcin
The maximum average degree $\mathrm{mad}(G)$ of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this paper we prove that for every $G$ and positive integer $k$ such that $\mathrm{mad}(G) \ge k$ there exists $S \subseteq V(G)$
Externí odkaz:
http://arxiv.org/abs/1909.10701