Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Socala, Arkadiusz"'
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
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
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance $d$ from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in ti
Externí odkaz:
http://arxiv.org/abs/1607.07906
In the multicoloring problem, also known as ($a$:$b$)-coloring or $b$-fold coloring, we are given a graph G and a set of $a$ colors, and the task is to assign a subset of $b$ colors to each vertex of G so that adjacent vertices receive disjoint color
Externí odkaz:
http://arxiv.org/abs/1607.03432
The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k
Externí odkaz:
http://arxiv.org/abs/1602.05608
Autor:
Cygan, Marek, Fomin, Fedor V., Golovnev, Alexander, Kulikov, Alexander S., Mihajlin, Ivan, Pachocki, Jakub, Socała, Arkadiusz
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph $G$ to graph $H$ cannot be done in time $|V(H)|^{o(|V(G)|)}$. We also show an exponential-time reduction from Graph Homomorphism to Subgr
Externí odkaz:
http://arxiv.org/abs/1602.05016
In the $k$-Leaf Out-Branching and $k$-Internal Out-Branching problems we are given a directed graph $D$ with a designated root $r$ and a nonnegative integer $k$. The question is to determine the existence of an outbranching rooted at $r$ that has at
Externí odkaz:
http://arxiv.org/abs/1509.01675
Subgraph Isomorphism is a very basic graph problem, where given two graphs $G$ and $H$ one is to check whether $G$ is a subgraph of $H$. Despite its simple definition, the Subgraph Isomorphism problem turns out to be very broad, as it generalizes pro
Externí odkaz:
http://arxiv.org/abs/1504.02876
Autor:
Socala, Arkadiusz
We study the complexity of the Channel Assignment problem. A major open problem asks whether Channel Assignment admits an $O(c^n)$-time algorithm, for a constant $c$ independent of the weights on the edges. We answer this question in the negative i.e
Externí odkaz:
http://arxiv.org/abs/1407.7162