Zobrazeno 1 - 10
of 129
pro vyhledávání: '"Kowalik, Lukasz"'
Autor:
Kowalik, Lukasz
In this paper we show that every graph $G$ of bounded maximum average degree ${\rm mad}(G)$ and with maximum degree $\Delta$ can be edge-colored using the optimal number of $\Delta$ colors in quasilinear time, whenever $\Delta\ge 2{\rm mad}(G)$. The
Externí odkaz:
http://arxiv.org/abs/2401.13839
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 show that the edges of any planar graph of maximum degree at most $9$ can be partitioned into $4$ linear forests and a matching. Combined with known results, this implies that the edges of any planar graph $G$ of odd maximum degree $\Delta\ge 9$ c
Externí odkaz:
http://arxiv.org/abs/2302.13312
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
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
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can be decreased by a popular $k$-opt move. Earlier work has shown that (i)
Externí odkaz:
http://arxiv.org/abs/1908.09325
Autor:
Kowalik, Łukasz, Socała, Arkadiusz
The fastest algorithms for edge coloring run in time $2^m n^{O(1)}$, where $m$ and $n$ are the number of edges and vertices of the input graph, respectively. For dense graphs, this bound becomes $2^{\Theta(n^2)}$. This is a somewhat unique situation,
Externí odkaz:
http://arxiv.org/abs/1804.02537
Publikováno v:
In Journal of Computer and System Sciences March 2022 124:112-128
Autor:
Bonamy, Marthe, Kowalik, Łukasz, Nederlof, Jesper, Pilipczuk, Michał, Socała, Arkadiusz, Wrochna, Marcin
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time $2^{o(t\log t)}\cdot n^{\mathcal{O}(1)}$ on general
Externí odkaz:
http://arxiv.org/abs/1707.01470
Given a traveling salesman problem (TSP) tour $H$ in graph $G$ a $k$-move is an operation which removes $k$ edges from $H$, and adds $k$ edges of $G$ so that a new tour $H'$ is formed. The popular $k$-OPT heuristics for TSP finds a local optimum by s
Externí odkaz:
http://arxiv.org/abs/1703.05559