25 citations · 27 across the 5 of their papers we have counts for
8 papers
Partitioning edges of a planar graph into linear forests and a matching
Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik +1
We show that the edges of any planar graph of maximum degree at most can be partitioned into linear forests and a matching. Combined with known results, this implies that t…
Improving TSP tours using dynamic programming over tree decomposition
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Given a traveling salesman problem (TSP) tour in graph a -move is an operation which removes edges from , and adds edges of so that a new tour is for…
Tight lower bounds for the complexity of multicoloring
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2
In the multicoloring problem, also known as (:)-coloring or -fold coloring, we are given a graph G and a set of colors, and the task is to assign a subset of color…
Linear kernels for outbranching problems in sparse digraphs
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +1
In the -Leaf Out-Branching and -Internal Out-Branching problems we are given a directed graph with a designated root and a nonnegative integer . The question is to…
Assigning channels via the meet-in-the-middle approach
Łukasz Kowalik, Arkadiusz Socała
We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the -bounded Channel Assignment (when the edge…
Counting thin subgraphs via packings faster than meet-in-the-middle time
Andreas Björklund, Petteri Kaski, Łukasz Kowalik
Vassilevska and Williams (STOC 2009) showed how to count simple paths on vertices and matchings on edges in an -vertex graph in time . In the same year,…
Constrained Multilinear Detection and Generalized Graph Motifs
Andreas Bjorklund, Petteri Kaski, Lukasz Kowalik
We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. As applica…
A Planar Linear Arboricity Conjecture
Marek Cygan, Lukasz Kowalik, Borut Luzar
The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. stated the Linear Arboricity Conjecture (LAC…