Lukasz Kowalik

  • University of Warsaw
  • Max Planck Institute for Informatics, Saarbrücken, Germany

According to our database1, Lukasz Kowalik authored at least 54 papers between 2002 and 2022.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Many-visits TSP revisited.
J. Comput. Syst. Sci., 2022

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Tight Lower Bounds for the Complexity of Multicoloring.
ACM Trans. Comput. Theory, 2019

Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ACM Trans. Algorithms, 2019

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

On the Fine-Grained Complexity of Rainbow Coloring.
SIAM J. Discret. Math., 2018

Approximation and Parameterized Complexity of Minimax Approval Voting.
J. Artif. Intell. Res., 2018

On Directed Feedback Vertex Set Parameterized by Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Tight Lower Bounds for List Edge Coloring.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time.
ACM Trans. Algorithms, 2017

Spotting Trees with Few Leaves.
SIAM J. Discret. Math., 2017

Improving TSP tours using dynamic programming over tree decomposition.
CoRR, 2017

Linear Kernels for Outbranching Problems in Sparse Digraphs.
Algorithmica, 2017

RobustSPAM for Inference from Noisy Longitudinal Data and Preservation of Privacy.
Proceedings of the 16th IEEE International Conference on Machine Learning and Applications, 2017

On finding rainbow and colorful paths.
Theor. Comput. Sci., 2016

A 13k-kernel for planar feedback vertex set via region decomposition.
Theor. Comput. Sci., 2016

Assigning Channels Via the Meet-in-the-Middle Approach.
Algorithmica, 2016

Constrained Multilinear Detection and Generalized Graph Motifs.
Algorithmica, 2016

Engineering Motif Search for Large Graphs.
Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, 2015

A 9k kernel for nonseparating independent set in planar graphs.
Theor. Comput. Sci., 2014

Beyond the Vizing's Bound for at Most Seven Colors.
SIAM J. Discret. Math., 2014

A 14k -Kernel for Planar Feedback Vertex Set via Region Decomposition.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Fast Witness Extraction Using a Decision Oracle.
Proceedings of the Algorithms - ESA 2014, 2014

Towards optimal kernel for connected vertex cover in planar graphs.
Discret. Appl. Math., 2013

Beyond the Shannon's Bound.
CoRR, 2013

Probably Optimal Graph Motifs.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

A Planar linear arboricity conjecture.
J. Graph Theory, 2012

Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

Channel assignment via fast zeta transform.
Inf. Process. Lett., 2011

35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality.
Algorithmica, 2011

An improved bound on the largest induced forests for triangle-free planar graphs.
Discret. Math. Theor. Comput. Sci., 2010

Improved induced matchings in sparse graphs.
Discret. Appl. Math., 2010

Fast 3-coloring Triangle-Free Planar Graphs.
Algorithmica, 2010

Approximating the Maximum 3- and 4-Edge-Colorable Subgraph.
Proceedings of the Algorithm Theory, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.
Proceedings of the Algorithms, 2010

A Planar Linear Arboricity Conjecture.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Deterministic 7/8-approximation for the metric maximum TSP.
Theor. Comput. Sci., 2009

Improved edge-coloring with three colors.
Theor. Comput. Sci., 2009

Exponential-time approximation of weighted set cover.
Inf. Process. Lett., 2009

Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Total-Coloring of Plane Graphs with Maximum Degree Nine.
SIAM J. Discret. Math., 2008

Exponential-Time Approximation of Hard Problems
CoRR, 2008

New Linear-Time Algorithms for Edge-Coloring Planar Graphs.
Algorithmica, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

A Generalization of Kotzig's Theorem and Its Application.
SIAM J. Discret. Math., 2007

Adjacency queries in dynamic sparse graphs.
Inf. Process. Lett., 2007

Oracles for bounded-length shortest paths in planar graphs.
ACM Trans. Algorithms, 2006

A Note on Scheduling Equal-Length Jobs to Maximize Throughput.
J. Sched., 2006

Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Short Cycles in Planar Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Short path queries in planar graphs in constant time.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A New 3-Color Criterion for Planar Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002