Research papers
See elsewhere
[dblp] | [Google scholar] | [University portal]
Jump to area
Exponential-time and parameterized algorithms | Approximation algorithms | Planar graphs | Other areas
Exponential-time and parameterized algorithms
-
The PACE 2020 Parameterized Algorithms and Computational Experiments
Challenge: Treedepth,
Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge and Piotr Wygocki
Proc. 15th International Symposium on Parameterized and Exact Computation, IPEC 2020,
[DOI] [benchmark instances repository] -
The Asymmetric Travelling Salesman Problem in Sparse Digraphs,
Lukasz Kowalik, Konrad Majewski
Proc. 15th International Symposium on Parameterized and Exact Computation, IPEC 2020,
[DOI] [arXiv] -
Many visits TSP revisited,
Lukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, Magnus
Wahlström.
Proc. 28th Annual European Symposium on Algorithms (ESA 2020),
[DOI] [arXiv] -
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving
TSP, Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen and Lukasz Kowalik.
Proc. 27th Annual European Symposium on Algorithms (ESA 2019)
[DOI] [arXiv] -
Tight Lower Bounds for List Edge Coloring, Lukasz Kowalik, Arkadiusz
Socala.
Proc. 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'18)
[arXiv] [DOI] [slides] -
On Directed Feedback Vertex Set parameterized by treewidth, Marthe
Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz
Socala, Marcin Wrochna.
Proc. 44th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), LNCS 11159, Springer, pp. 65-78.
[arXiv] [DOI] -
Improving TSP tours using dynamic programming over tree decomposition, with
Marek Cygan and Arkadiusz Socala.
ACM Transactions on Algorithms, vol. 15(4), pp. 54:1--54:19, 2019.
[arXiv] [DOI]
Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017). Best paper award.
[DOI] [slides] -
Tight lower bounds for the complexity of multicoloring, with
Marthe Bonamy, Michal Pilipczuk, Arkadiusz Socala, and
Marcin Wrochna
ACM Transactions on Computation Theory, 11 (2019), pp. 13:1-13:19
[DOI] [arXiv]
Conference version: Proc. 25th Annual European Symposium on Algorithms (ESA 2017).
[DOI] -
Approximation and Parameterized Complexity of Minimax Approval Voting, with
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Journal of Artificial Intelligence Research, 63 (2018) 495-513
[DOI] [arXiv]
Conference version: Proc. 31st AAAI Conference on Artificial Intelligence (AAAI'17), pp. 459--465, AAAI Press, 2017.
[DOI] -
On the fine-grained complexity of rainbow coloring, with
Juho Lauri and Arkadiusz Socala
SIAM J. Discrete Math, 32(3), 1672-1705 (2018)
[arXiv] [DOI]
Conference version: Proc. 24th Annual European Symposium on Algorithms (ESA 2016)
[DOI] -
On finding rainbow and colorful paths, with
Juho Lauri
Theor. Comput. Sci. 628: 110-114 (2016)
[Publisher's version] -
Linear kernels for outbranching problems in sparse digraphs, with
Marthe Bonamy, Michal Pilipczuk and Arkadiusz Socala
Algorithmica 79(1): 159-188 (2017).
[arXiv] [BibTeX entry] [DOI]
Conference version: Proc IPEC'15, LNCS vol 9134, pp. 199-211, 2015.
[BibTeX entry] [DOI] -
Spotting Trees with Few Leaves, with
Andreas Björklund, Vikram Kamat and Meirav Zehavi
SIAM Journal on Discrete Mathematics, 2017, Vol. 31, No. 2 : pp. 687-713.
[DOI] [arXiv] [talk]
Conference version: Proc. ICALP 2015, pp. 243-255.
[BibTeX entry] [DOI] [slides] -
Constrained Multilinear Detection and Generalized Graph Motifs, with
Andreas Björklund, Petteri Kaski
Algorithmica 74(2): 947-967 (2016)
(Extended, generalized version of our STACS 2013 paper)
[PDF] [Publisher's version] -
Engineering Motif Search for Large Graphs, with
Andreas Björklund, Petteri Kaski, Juho Lauri
Proc. 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, SIAM, 2015, pp. 104-118.
[PDF] [Publisher's version] -
A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition, with
Marthe Bonamy
Theor. Comput. Sci. 645: 25-40 (2016)
[arXiv] [DOI]
Conference version: A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition Proc. 9th International Symposium on Parameterized and Exact Computation, IPEC'14, LNCS vol 8894, Springer, 97-109, 2014.
[slides] -
Fast Witness
Extraction Using a Decision Oracle, with Andreas Björklund and Petteri Kaski
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160.
[Publisher's version] [BibTeX entry] [slides] -
Assigning channels via the
meet-in-the-middle approach, with Arkadiusz Socala,
Algorithmica 74(4): 1435-1452 (2016) (open access).
[arXiv] [PDF] [DOI]
Conference version: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), LNCS 8503, 2014, pp. 282-293.
[Publisher's version] -
Counting thin
subgraphs via packings faster than meet-in-the-middle time, with Andreas Björklund
and Petteri Kaski,
ACM Trans. Algorithms. 13(4): 48:1-48:26 (2017)
[arXiv] [DOI]
Conference version: ACM-SIAM Symposium on Discrete Algorithms (SODA 2014),
[DOI] - Probably Optimal Graph Motifs,
with Andreas Björklund and Petteri Kaski
Proc. 30th Symposium on Theoretical Aspects of Computer Science (STACS 2013),
LIPIcs, 20-31, 2013.
[arXiv] [Publisher's version] [BibTeX entry] [slides] - Nonblocker in H-minor free graphs: kernelization meets
discharging
Proc. 7th International Symposium on Parameterized and Exact Computation (IPEC 2012),
LNCS 7535, 61-72, 2012.
[arXiv] [Publisher's version] [slides] - A 9k kernel for nonseparating independent set in planar graphs,
with Marcin Mucha
Theoretical Computer Science, Vol. 516, 2013, 86-95. .
Conference version: Proc. 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012), LNCS 7551, 160-171, 2012.
[arXiv] [Publisher's version] [slides] - Towards optimal kernel for connected vertex cover in
planar graphs with Marcin Pilipczuk and Karol Suchan.
Discr. Appl. Math., Vol. 161, 1154-1161, 2013.
[arXiv] [Publisher's version] -
Channel Assignment via Fast Zeta Transform,
with Marek Cygan
Information Processing Letters, Vol. 111, No. 15, 2011, 727-730.
[arXiv] [Publisher's version] -
Improved induced matchings in sparse graphs,
with and Rok Erman, Matjaz Krnc, Tomasz Walen
Discr. Appl. Math., Vol. 158, No. 18, pp 1994-2003, 2010.
[PDF] [Publisher's version]
Conference version: Proc. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), LNCS 5917, 134-138, 2009. -
Exponential-Time Approximation of Weighted Set Cover
with Marek Cygan and Mateusz Wykurz
Information Processing Letters Vol. 109, 2009, 957-961.
[PDF] [Publisher's version]
The above paper contains selected results from the earlier technical report:
Exponential-Time Approximation of Hard Problems, with Marek Cygan, Marcin Pilipczuk and Mateusz Wykurz
[arXiv] [slides] - Improved Edge Coloring with Three Colors
Theoretical Computer Science, Vol. 410, No. 38-40, 2009, 3733-3742.
[BibTeX entry] [PDF] [Publisher's version]
Conference version: Proc. 32nd Int. Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2006) , LNCS 4271, 2006, 90-101.
[BibTeX entry] [Publisher's version] [slides]
Approximation algorithms
-
Beyond the Shannon's Bound, with Michał Farnik and Arkadiusz Socała
[arXiv] -
Beyond the Vizing's bound for at most seven colors, with Marcin Kamiński
SIAM J. Discrete Math., vol. 28, no. 3, 2014, 1334-1362.
[arXiv] [Publisher's version] -
Approximating the maximum 3- and 4-edge-colorable subgraph,
with Marcin Kamiński,
Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), LNCS 6139, 2010, pp. 395-407.
[BiBTeX entry] [Electronic version] [slides] - Fast Approximation in Subspaces by Doubling Metric
Decomposition,
with Marek Cygan, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski,
Proc. 18th Annual European Symposium on Algorithms (ESA 2010), LNCS 6346, 2010, pp. 72-83.
[arXiv] [Electronic version] - Two approximation algorithms for ATSP with strengthened triangle inequality,
with Marcin Mucha,
Proc. 11th International Workshop on Algorithms and Data Structures (WADS 2009), LNCS 5664, 2009, pp. 471-482.
[PDF] [BibTeX entry] [Publisher's version] - Deterministic 7/8-approximation for the Metric Maximum TSP, with Marcin
Mucha
Theoretical Computer Science, Vol. 410, 2009, 5000-5009.
[BibTeX entry] [PDF] [Electronic version]
Conference version: Proc. APPROX-RANDOM 2008, LNCS 5171, 2008, pp. 132-145.
[Electronic version] - 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality,
with Marcin Mucha,
Full version: Algorithmica, Volume 59, No. 2, 2011, pp 240-255.
[PDF] [Publisher's version]
Conference version: Proc. 10th International Workshop on Algorithms and Data Structures (WADS 2007), LNCS 4619, 2007, pp. 589-600.
[BibTeX entry] [PS] [PDF] [Publisher's version] - Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), LNCS 4288, 2006, 557-566.
[BibTeX entry] [PS] [PDF] [Publisher's version] [slides]
Planar graphs: algorithms and properties
- A Planar Linear Arboricity Conjecture,
with Marek Cygan, Jian-Feng Hou, Borut Luzar and Jian-Liang Wu.
J. Graph Theory, vol. 69, no. 4, 2012, pp. 403-425.
[Publisher's version]
Conference version (authors: Marek Cygan, Lukasz Kowalik, Borut Luzar): Proc. 7th International Conference on Algorithms and Complexity (CIAC 2010), LNCS 6078, 2010, pp. 204-216.
arXiv:0912.5528, 2009.
[PDF] [Publisher's version] - An improved bound on the largest induced forests for triangle-free planar
graphs, with Borut Luzar and Riste Skrekovski
Discrete Mathematics & Theoretical Computer Science Vol. 12, No. 1, 87-100, 2010.
[PDF] [BibTeX entry] [Publisher's version] - Total colouring of plane graphs with maximum degree nine, with Jean-Sebastien Sereni and Riste
Skrekovski,
SIAM J. Discrete Math., Vol. 22, No. 4, 2008, 1462--1479.
[BibTeX entry] [PDF] [Publisher's version] - New Linear-Time Algortihms for Edge-Coloring Planar Graphs,
with Richard Cole
Algorithmica, Vol. 50, No. 3, 2008, 351--368 .
[BibTeX entry] [PS] [PDF] [Publisher's version] - A Generalization of Kotzig's Theorem and its Application,
with Richard Cole, Riste Skrekovski,
SIAM J. Discrete Math., Vol. 21, No. 1, 2007, 93--106.
[BibTeX entry] [PS] [PDF] [Publisher's version] - Oracles for Bounded Length Shortest Paths in Planar Graphs, with Maciej
Kurowski
ACM Transactions on Algorithms, Vol. 2, No. 3, 2006, 335-363.
[BibTeX entry] [PS] [PDF] [Publisher's version] - Fast 3-Coloring Triangle-Free Planar Graphs,
Algorithmica, Vol. 58, No. 3, 2010, 770-789.
[PDF] [Publisher's version]
Conference version: Proc. 12th Annual European Symposium on Algorithms (ESA 2004), LNCS 3221, 2004, 436-447.
[BibTeX entry] [Publisher's version] - More on Light Graphs in 3-Connected Plane Graphs Without
Triangular or Quadrangular Faces,
Technical Report no. 275, Institute of Informatics, Warsaw University, 2004.
[BibTeX entry] [PS] [PDF] - Short Cycles in Planar Graphs,
Proc. 29th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2003), LNCS 2880, 2003, 284-296.
[BibTeX entry] [PS] [PDF] [Publisher's version] - Short Path Queries in Planar Graphs in Constant Time,
with M.Kurowski,
Proc. 35th Symp. Theory of Computing (STOC 2003), 2003, 143-148.
[BibTeX entry] [PS] [PDF] [Publisher's version] - A New 3-Color Criterion For Planar Graphs, with K. Diks and M.
Kurowski,
Proc. 28th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2002), LNCS 2573, 2002, 138-149.
[BibTeX entry] [PS] [PDF] [Publisher's version]
Other areas
- Adjacency Queries in Dynamic Sparse Graphs
Information Processing Letters, Vol. 102, No. 5, 2007, 191--195
[BibTeX entry] [PS] [PDF] [Publisher's version] - A Note on Scheduling Equal-Length Jobs to Maximize Throughput,
with M. Chrobak, C. Durr, W. Jawor, M. Kurowski
Short version: Journal on Scheduling, Vol. 9, No. 1, 2006, 71-73.
[BibTeX entry] [Publisher's version]
Extended version: arXiv.org e-Print archive, cs.DS/0410046, 2004.
[BibTeX entry] [PS] [PDF]
PhD Thesis
Algorytmiczne problemy sciezkowe w grafach planarnych (rozprawa doktorska),Algorithmic Path Problems in Planar Graphs (PhD Thesis, in Polish)
Warsaw University, 2005.
[BibTeX entry] [PS] [PDF]
(The thesis is based on papers "Oracles for bounded length shortest paths in planar graphs", "Fast 3-coloring triangle-free planar graphs" and "Short cycles in planar graphs")
Popular science
- Problem komiwojażera w praktyce,
Delta, 2 / 2020. (in Polish)
[PDF]
- Problem izomorfizmu grafów, Delta, 12 / 2018. (in Polish) [PDF]
- Programy liniowe, gry i algorytmy, Delta, 8 / 2013. (in Polish) [PDF]
- O notacji asymptotycznej w analizie algorytmów, Delta, 1 / 2008, 4-5. (in Polish) [PDF]
- Spacery po mostach i przejażdżki po mieście, Software 2.0, 7 / 2002. (in Polish) [PDF]