Lukasz Kowalik

99 papers A* 3A 10B 14C 2Journal 60Unranked 9
YearRankTypeTitle / Venue / Authors
2025 J jnl
The planar edge-coloring theorem of Vizing in O(n log n) time.
CoRR
Patryk Jedrzejczak, Lukasz Kowalik
2024 — conf
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.
SOSA
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2024 A conf
Edge-Coloring Sparse Graphs with Δ Colors in Quasilinear Time.
ESA
Lukasz Kowalik
2024 J jnl
Edge-coloring sparse graphs with Δ colors in quasilinear time.
CoRR
Lukasz Kowalik
2023 J jnl
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.
CoRR
Lukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michal Pilipczuk, Marek Sokolowski
2023 J jnl
Partitioning edges of a planar graph into linear forests and a matching.
CoRR
Marthe Bonamy, Jadwiga Czyzewska, Lukasz Kowalik, Michal Pilipczuk
2023 J jnl
Partitioning edges of a planar graph into linear forests and a matching.
J. Graph Theory
Marthe Bonamy, Jadwiga Czyzewska, Lukasz Kowalik, Michal Pilipczuk
2022 J jnl
Many-visits TSP revisited.
J. Comput. Syst. Sci.
Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström
2021 B ed.
Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers
WG
Lukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
2020 A conf
Many Visits TSP Revisited.
ESA
Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström
2020 J jnl
Many visits TSP revisited.
CoRR
Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus Wahlström
2020 B conf
The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
IPEC
Lukasz Kowalik, Konrad Majewski
2020 J jnl
The Asymmetric Travelling Salesman Problem in Sparse Digraphs.
CoRR
Lukasz Kowalik, Konrad Majewski
2020 B conf
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
IPEC
Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki
2019 A conf
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.
ESA
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik
2019 J jnl
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.
CoRR
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik
2019 J jnl
Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ACM Trans. Algorithms
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2019 J jnl
Tight Lower Bounds for the Complexity of Multicoloring.
ACM Trans. Comput. Theory
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2018 J jnl
Approximation and Parameterized Complexity of Minimax Approval Voting.
J. Artif. Intell. Res.
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2018 B conf
On Directed Feedback Vertex Set Parameterized by Treewidth.
WG
Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2018 J jnl
On the Fine-Grained Complexity of Rainbow Coloring.
SIAM J. Discret. Math.
Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
2018 — conf
Tight Lower Bounds for List Edge Coloring.
SWAT
Lukasz Kowalik, Arkadiusz Socala
2018 J jnl
Tight Lower Bounds for List Edge Coloring.
CoRR
Lukasz Kowalik, Arkadiusz Socala
2017 A* conf
Approximation and Parameterized Complexity of Minimax Approval Voting.
AAAI
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2017 J jnl
Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time.
ACM Trans. Algorithms
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2017 A conf
Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ESA
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2017 J jnl
Improving TSP tours using dynamic programming over tree decomposition.
CoRR
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
2017 J jnl
Linear Kernels for Outbranching Problems in Sparse Digraphs.
Algorithmica
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala
2017 J jnl
On Directed Feedback Vertex Set parameterized by treewidth.
CoRR
Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2017 C conf
RobustSPAM for Inference from Noisy Longitudinal Data and Preservation of Privacy.
ICMLA
Anna Palczewska, Jan Palczewski, Georgios Aivaliotis, Lukasz Kowalik
2017 J jnl
Spotting Trees with Few Leaves.
SIAM J. Discret. Math.
Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2017 A conf
Tight Lower Bounds for the Complexity of Multicoloring.
ESA
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2016 J jnl
A 13k-kernel for planar feedback vertex set via region decomposition.
Theor. Comput. Sci.
Marthe Bonamy, Lukasz Kowalik
2016 J jnl
Approximation and Parameterized Complexity of Minimax Approval Voting.
CoRR
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
2016 J jnl
Assigning Channels Via the Meet-in-the-Middle Approach.
Algorithmica
Lukasz Kowalik, Arkadiusz Socala
2016 J jnl
Constrained Multilinear Detection and Generalized Graph Motifs.
Algorithmica
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2016 J jnl
On finding rainbow and colorful paths.
Theor. Comput. Sci.
Lukasz Kowalik, Juho Lauri
2016 A conf
On the Fine-Grained Complexity of Rainbow Coloring.
ESA
Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
2016 J jnl
On the fine-grained complexity of rainbow coloring.
CoRR
Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
2016 J jnl
Tight lower bounds for the complexity of multicoloring.
CoRR
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, Marcin Wrochna
2015 A conf
Engineering Motif Search for Large Graphs.
ALENEX
Andreas Björklund, Petteri Kaski, Lukasz Kowalik, Juho Lauri
2015 J jnl
Fast Witness Extraction Using a Decision Oracle.
CoRR
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2015 B conf
Linear Kernels for Outbranching Problems in Sparse Digraphs.
IPEC
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala
2015 J jnl
Linear kernels for outbranching problems in sparse digraphs.
CoRR
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala
2015 — book
Parameterized Algorithms
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
2015 — conf
Spotting Trees with Few Leaves.
ICALP (1)
Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2015 J jnl
Spotting Trees with Few Leaves.
CoRR
Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
2014 J jnl
A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition.
CoRR
Marthe Bonamy, Lukasz Kowalik
2014 B conf
A 14k -Kernel for Planar Feedback Vertex Set via Region Decomposition.
IPEC
Marthe Bonamy, Lukasz Kowalik
2014 J jnl
A 9k kernel for nonseparating independent set in planar graphs.
Theor. Comput. Sci.
Lukasz Kowalik, Marcin Mucha
2014 — conf
Assigning Channels via the Meet-in-the-Middle Approach.
SWAT
Lukasz Kowalik, Arkadiusz Socala
2014 J jnl
Assigning channels via the meet-in-the-middle approach.
CoRR
Lukasz Kowalik, Arkadiusz Socala
2014 J jnl
Beyond the Vizing's Bound for at Most Seven Colors.
SIAM J. Discret. Math.
Marcin Jakub Kaminski, Lukasz Kowalik
2014 A* conf
Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time.
SODA
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2014 A conf
Fast Witness Extraction Using a Decision Oracle.
ESA
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2013 J jnl
Beyond the Shannon's Bound.
CoRR
Michal Farnik, Lukasz Kowalik, Arkadiusz Socala
2013 J jnl
Counting thin subgraphs via packings faster than meet-in-the-middle time.
CoRR
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2013 A conf
Probably Optimal Graph Motifs.
STACS
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2013 J jnl
Towards optimal kernel for connected vertex cover in planar graphs.
Discret. Appl. Math.
Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan
2012 B conf
A 9k Kernel for Nonseparating Independent Set in Planar Graphs.
WG
Lukasz Kowalik, Marcin Mucha
2012 J jnl
A 9k kernel for nonseparating independent set in planar graphs
CoRR
Lukasz Kowalik, Marcin Mucha
2012 J jnl
A Planar linear arboricity conjecture.
J. Graph Theory
Marek Cygan, Jianfeng Hou, Lukasz Kowalik, Borut Luzar, Jian-Liang Wu
2012 J jnl
Beyond the Vizing's bound for at most seven colors
CoRR
Marcin Kaminski, Lukasz Kowalik
2012 B conf
Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging.
IPEC
Lukasz Kowalik
2012 J jnl
Nonblocker in H-minor free graphs: kernelization meets discharging
CoRR
Lukasz Kowalik
2012 J jnl
Probably Optimal Graph Motifs
CoRR
Andreas Björklund, Petteri Kaski, Lukasz Kowalik
2011 J jnl
35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality.
Algorithmica
Lukasz Kowalik, Marcin Mucha
2011 J jnl
Channel Assignment via Fast Zeta Transform
CoRR
Marek Cygan, Lukasz Kowalik
2011 J jnl
Channel assignment via fast zeta transform.
Inf. Process. Lett.
Marek Cygan, Lukasz Kowalik
2011 J jnl
Towards optimal kernel for connected vertex cover in planar graphs
CoRR
Lukasz Kowalik, Marcin Pilipczuk, Karol Suchan
2010 C conf
A Planar Linear Arboricity Conjecture.
CIAC
Marek Cygan, Lukasz Kowalik, Borut Luzar
2010 J jnl
An improved bound on the largest induced forests for triangle-free planar graphs.
Discret. Math. Theor. Comput. Sci.
Lukasz Kowalik, Borut Luzar, Riste Skrekovski
2010 — conf
Approximating the Maximum 3- and 4-Edge-Colorable Subgraph.
SWAT
Marcin Kaminski, Lukasz Kowalik
2010 J jnl
Fast 3-coloring Triangle-Free Planar Graphs.
Algorithmica
Lukasz Kowalik
2010 — conf
Fast Approximation in Subspaces by Doubling Metric Decomposition.
ESA (1)
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2010 J jnl
Improved induced matchings in sparse graphs.
Discret. Appl. Math.
Rok Erman, Lukasz Kowalik, Matjaz Krnc, Tomasz Walen
2009 J jnl
Deterministic 7/8-approximation for the metric maximum TSP.
Theor. Comput. Sci.
Lukasz Kowalik, Marcin Mucha
2009 J jnl
Exponential-time approximation of weighted set cover.
Inf. Process. Lett.
Marek Cygan, Lukasz Kowalik, Mateusz Wykurz
2009 J jnl
Fast Approximation in Subspaces by Doubling Metric Decomposition
CoRR
Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski
2009 — conf
Improved Induced Matchings in Sparse Graphs.
IWPEC
Rok Erman, Lukasz Kowalik, Matjaz Krnc, Tomasz Walen
2009 J jnl
Improved edge-coloring with three colors.
Theor. Comput. Sci.
Lukasz Kowalik
2009 B conf
Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.
WADS
Lukasz Kowalik, Marcin Mucha
2008 — conf
08431 Open Problems - Moderately Exponential Time Algorithms.
Moderately Exponential Time Algorithms
Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan M. M. van Rooij, Ryan Williams
2008 — conf
Deterministic 7/8-Approximation for the Metric Maximum TSP.
APPROX-RANDOM
Lukasz Kowalik, Marcin Mucha
2008 J jnl
Exponential-Time Approximation of Hard Problems
CoRR
Marek Cygan, Lukasz Kowalik, Marcin Pilipczuk, Mateusz Wykurz
2008 J jnl
New Linear-Time Algorithms for Edge-Coloring Planar Graphs.
Algorithmica
Richard Cole, Lukasz Kowalik
2008 J jnl
Total-Coloring of Plane Graphs with Maximum Degree Nine.
SIAM J. Discret. Math.
Lukasz Kowalik, Jean-Sébastien Sereni, Riste Skrekovski
2007 B conf
35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality.
WADS
Lukasz Kowalik, Marcin Mucha
2007 J jnl
A Generalization of Kotzig's Theorem and Its Application.
SIAM J. Discret. Math.
Richard Cole, Lukasz Kowalik, Riste Skrekovski
2007 J jnl
Adjacency queries in dynamic sparse graphs.
Inf. Process. Lett.
Lukasz Kowalik
2006 J jnl
A Note on Scheduling Equal-Length Jobs to Maximize Throughput.
J. Sched.
Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, Maciej Kurowski
2006 B conf
Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures.
ISAAC
Lukasz Kowalik
2006 B conf
Improved Edge-Coloring with Three Colors.
WG
Lukasz Kowalik
2006 J jnl
Oracles for bounded-length shortest paths in planar graphs.
ACM Trans. Algorithms
Lukasz Kowalik, Maciej Kurowski
2004 J jnl
A Note on Scheduling Equal-Length Jobs to Maximize Throughput
CoRR
Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, Maciej Kurowski
2004 A conf
Fast 3-Coloring Triangle-Free Planar Graphs.
ESA
Lukasz Kowalik
2003 B conf
Short Cycles in Planar Graphs.
WG
Lukasz Kowalik
2003 A* conf
Short path queries in planar graphs in constant time.
STOC
Lukasz Kowalik, Maciej Kurowski
2002 B conf
A New 3-Color Criterion for Planar Graphs.
WG
Krzysztof Diks, Lukasz Kowalik, Maciej Kurowski