Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Majewski, Konrad"'
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
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
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
Autor:
Briański, Marcin, Joret, Gwenaël, Majewski, Konrad, Micek, Piotr, Seweryn, Michał T., Sharma, Roohani
Publikováno v:
Combinatorica, 43:659--664, 2023
The circumference of a graph $G$ is the length of a longest cycle in $G$, or $+\infty$ if $G$ has no cycle. Birmel\'e (2003) showed that the treewidth of a graph $G$ is at most its circumference minus $1$. We strengthen this result for $2$-connected
Externí odkaz:
http://arxiv.org/abs/2211.11410
Max Weight Independent Set in graphs with no long claws: An analog of the Gy\'arf\'as' path argument
Autor:
Majewski, Konrad, Masařík, Tomáš, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Marcin, Rzążewski, Paweł, Sokołowski, Marek
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomass\'{e}, SODA 2020] and provide a subexponential-time algor
Externí odkaz:
http://arxiv.org/abs/2203.04836
Let $\varphi$ be a sentence of $\mathsf{CMSO}_2$ (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph $G$ that is u
Externí odkaz:
http://arxiv.org/abs/2107.06232
Autor:
Kowalik, Łukasz, Majewski, Konrad
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time $O^*(2^n)$ developed almost 60 years ago by Bellm
Externí odkaz:
http://arxiv.org/abs/2007.12120
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Kowalik, ��ukasz, Majewski, Konrad
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time $O^*(2^n)$ developed almost 60 years ago by Bellm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::66ca8eccfa6dcf498d8731005b3694f4