25 citations · 27 across the 5 of their papers we have counts for
6 papers · 1 filter
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…