Lukasz Kowalik

CoRR, July, 2025

2024

Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Edge-Coloring Sparse Graphs with Δ Colors in Quasilinear Time.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Partitioning edges of a planar graph into linear forests and a matching.

[BibT_eX]

[DOI]

J. Graph Theory, November, 2023

2020

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

[BibT_eX]

[DOI]

Konrad Majewski

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Many Visits TSP Revisited.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

On Directed Feedback Vertex Set Parameterized by Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Tight Lower Bounds for List Edge Coloring.

[BibT_eX]

[DOI]

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

2017

Improving TSP tours using dynamic programming over tree decomposition.

[BibT_eX]

[DOI]

CoRR, 2017

RobustSPAM for Inference from Noisy Longitudinal Data and Preservation of Privacy.

[BibT_eX]

[DOI]

Proceedings of the 16th IEEE International Conference on Machine Learning and Applications, 2017

Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Tight Lower Bounds for the Complexity of Multicoloring.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Approximation and Parameterized Complexity of Minimax Approval Voting.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

On finding rainbow and colorful paths.

[BibT_eX]

[DOI]

Juho Lauri

Theor. Comput. Sci., 2016

A 13k-kernel for planar feedback vertex set via region decomposition.

[BibT_eX]

[DOI]

Marthe Bonamy

Theor. Comput. Sci., 2016

Constrained Multilinear Detection and Generalized Graph Motifs.

[BibT_eX]

[DOI]

Algorithmica, 2016

On the Fine-Grained Complexity of Rainbow Coloring.

[BibT_eX]

[DOI]

Juho Lauri

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Linear Kernels for Outbranching Problems in Sparse Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

Spotting Trees with Few Leaves.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Engineering Motif Search for Large Graphs.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, 2015

Parameterized Algorithms

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-319-21275-3, 2015

2014

Beyond the Vizing's Bound for at Most Seven Colors.

[BibT_eX]

[DOI]

Marcin Jakub Kaminski

SIAM J. Discret. Math., 2014

Assigning Channels via the Meet-in-the-Middle Approach.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

A 14k -Kernel for Planar Feedback Vertex Set via Region Decomposition.

[BibT_eX]

[DOI]

Marthe Bonamy

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Fast Witness Extraction Using a Decision Oracle.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

2013

Towards optimal kernel for connected vertex cover in planar graphs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Karol Suchan

Discret. Appl. Math., 2013

Beyond the Shannon's Bound.

[BibT_eX]

[DOI]

Michal Farnik

CoRR, 2013

Probably Optimal Graph Motifs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

A Planar linear arboricity conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 2012

A 9k Kernel for Nonseparating Independent Set in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

Channel assignment via fast zeta transform.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

2010

An improved bound on the largest induced forests for triangle-free planar graphs.

[BibT_eX]

[DOI]

Borut Luzar

Riste Skrekovski

Discret. Math. Theor. Comput. Sci., 2010

Approximating the Maximum 3- and 4-Edge-Colorable Subgraph.

[BibT_eX]

[DOI]

Marcin Kaminski

Proceedings of the Algorithm Theory, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

A Planar Linear Arboricity Conjecture.

[BibT_eX]

[DOI]

Borut Luzar

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

Exponential-time approximation of weighted set cover.

[BibT_eX]

[DOI]

Mateusz Wykurz

Inf. Process. Lett., 2009

Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Improved Induced Matchings in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

2008

Total-Coloring of Plane Graphs with Maximum Degree Nine.

[BibT_eX]

[DOI]

Jean-Sébastien Sereni

Riste Skrekovski

SIAM J. Discret. Math., 2008

Exponential-Time Approximation of Hard Problems

[BibT_eX]

[DOI]

CoRR, 2008

New Linear-Time Algorithms for Edge-Coloring Planar Graphs.

[BibT_eX]

[DOI]

Richard Cole

Algorithmica, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.

[BibT_eX]

[DOI]

Johan M. M. van Rooij

Ryan Williams

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

Deterministic 7/8-Approximation for the Metric Maximum TSP.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

A Generalization of Kotzig's Theorem and Its Application.

[BibT_eX]

[DOI]

Richard Cole

Riste Skrekovski

SIAM J. Discret. Math., 2007

Adjacency queries in dynamic sparse graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

2006

Oracles for bounded-length shortest paths in planar graphs.

[BibT_eX]

[DOI]

Maciej Kurowski

ACM Trans. Algorithms, 2006

A Note on Scheduling Equal-Length Jobs to Maximize Throughput.

[BibT_eX]

[DOI]

J. Sched., 2006

Improved Edge-Coloring with Three Colors.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2004

Fast 3-Coloring Triangle-Free Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

2003

Short Cycles in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Short path queries in planar graphs in constant time.

[BibT_eX]

[DOI]

Maciej Kurowski

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

A New 3-Color Criterion for Planar Graphs.

[BibT_eX]

[DOI]

Krzysztof Diks