Dr. Konrad Kazimierz Dąbrowski


Email: konrad.dabrowski at durham.ac.uk
Address:
School of Engineering and Computing Sciences
Durham University
Science Laboratories
South Road
Durham
DH1 3LE
UK

ACiD - Algorithms and Complexity in Durham

Picture of me



I am a research associate supervised by Prof. Daniel Paulusma and Prof. Iain Stewart, funded by EPSRC grant EP/K025090/1 "Detecting Induced Graph Patterns". I work mostly on graph structure and graph algorithms in restricted graph classes (from both a parameterized and non-parameterized point of view).

I completed my PhD in 2012, supervised by Prof. Vadim Lozin. After that, I worked for six months as a research associate supervised by Prof. Daniel Paulusma and Dr. George Mertzios, funded by EPSRC grant EP/G043434/1 "Algorithmic Aspects of Graph Coloring". I then worked for six months as a research associate supervised by Prof. M. Demange, funded by ANR grant TODO ANR 09-EMER-010 "Time Versus Optimality in Discrete Optimization".

Academic Responsibilities
I teach part of the Algorithms and Complexity sub-module of COMP2181 Theory of Computation.

I previosuly taught part of the Logic and Discrete Structures sub-module of COMP1021 Mathematics for Computer Science.
I organised the ACiD Research Seminars and the Computer Science Junior Seminars.

Journal Publications
Bounding Clique-Width via Perfect Graphs,
K.K. Dabrowski, S. Huang and D. Paulusma,
Journal of Computer and System Sciences, (arXiv:1406.6298) (link) (in press)

Bounding the Clique-Width of H-free Split Graphs,
A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,
Discrete Applied Mathematics, Volume 211, (2016), pp. 30-39 (arXiv:1509.04273) (link)

Combinatorics and algorithms for augmenting graphs,
K.K. Dabrowski, V.V. Lozin, D. de Werra and V. Zamaraev,
Graphs and Combinatorics, Volume 32(4), (2016), pp. 1339-1352 (arXiv:1410.8774) (link)

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs,
K.K. Dabrowski and D. Paulusma,
The Computer Journal, Volume 59(5), (2016), pp. 650-666 (arXiv:1405.7092) (link)

Editing to Eulerian Graphs,
K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma,
Journal of Computer and System Sciences, Volume 82(2), (2016), pp. 213-228 (arXiv:1410.6863) (link)

Classifying the Clique-Width of H-Free Bipartite Graphs,
K.K. Dabrowski and D. Paulusma,
Discrete Applied Mathematics, Volume 200, (2016), pp. 43-51 (arXiv:1402.7060) (link)

Stable-Pi Partitions of Graphs,
K.K. Dabrowski, V.V. Lozin and J. Stacho,
Discrete Applied Mathematics, Volume 182, (2015), pp. 104-114 (preprint) (link)

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs,
K.K. Dabrowski, P.A. Golovach and D. Paulusma,
Theoretical Computer Science, Volume 522, (2014), pp. 34-43 (preprint) (link)

New Results on Maximum Induced Matchings in Bipartite Graphs and Beyond,
K.K. Dabrowski, M. Demange and V.V. Lozin,
Theoretical Computer Science, Volume 478, (2013), pp. 33-40 (preprint) (link)

On factorial properties of chordal bipartite graphs,
K. Dabrowski, V.V. Lozin, and V. Zamaraev,
Discrete Mathematics, Volume 312, (16) (2012), pp. 2457-2465 (preprint) (link)

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number,
K. Dabrowski, V.V. Lozin, H. Müller and D. Rautenbach,
Journal of Discrete Algorithms, 14 (2012) pp. 207-213 (preprint) (link)

Colouring vertices of triangle-free graphs without forests,
K. Dabrowski, V.V. Lozin, R. Raman and B. Ries,
Discrete Mathematics, 312 (7) (2012) pp. 1372-1385 (preprint) (link)

Conference Publications
Well-quasi-ordering versus clique-width: new results on bigenic classes,
K.K. Dabrowski, V.V. Lozin and D. Paulusma,
Lecture Notes in Computer Science, 9843 (Proceedings of IWOCA 2016) (to appear)

Colouring Diamond-free Graphs,
K.K. Dabrowski, F. Dross, and D. Paulusma,
Leibniz International Proceedings in Informatics (LIPIcs), 53 (2016) pp. 16:1--16:14 (Proceedings of SWAT 2016) (arXiv:1512.07849) (link)

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs,
K.K. Dabrowski, F. Dross, M. Johnson and D. Paulusma,
Lecture Notes in Computer Science, 9538 (2016) pp. 100-111 (Proceedings of IWOCA 2015) (arXiv:1506.06564) (link)

Bounding the Clique-Width of H-free Split Graphs,
A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,
Electronic Notes in Discrete Mathematics, 49 (2015) pp. 497-503 (Proceedings of EuroComb 2015) (arXiv:1509.04273) (link)

Bounding the Clique-Width of H-free Chordal Graphs,
A. Brandstädt, K.K. Dabrowski, S. Huang and D. Paulusma,
Lecture Notes in Computer Science, 9235 (2015) pp. 139-150 (Proceedings of MFCS 2015, Part II) (arXiv:1502.06948) (link)

Editing to a Planar Graph of Given Degrees,
K.K. Dabrowski, P.A. Golovach, P. van 't Hof, D. Paulusma and D.M. Thilikos,
Lecture Notes in Computer Science, 9139 (2015) pp. 143-156 (Proceedings of CSR 2015) (arXiv:1508.02773) (link)

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs,
K.K. Dabrowski and D. Paulusma,
Lecture Notes in Computer Science, 9079 (2015) pp. 167-181 (Proceedings of CIAC 2015) (arXiv:1405.7092) (link)

Bounding Clique-Width via Perfect Graphs,
K.K. Dabrowski, S. Huang and D. Paulusma,
Lecture Notes in Computer Science, 8977 (2015) pp. 676-688 (Proceedings of LATA 2015) (arXiv:1406.6298) (link)

Editing to Eulerian Graphs,
K.K. Dabrowski, P.A. Golovach, P. van 't Hof and D. Paulusma,
Leibniz International Proceedings in Informatics (LIPIcs), 29 (2014) pp. 97-108 (Proceedings of FSTTCS 2014) (arXiv:1410.6863) (link)

Classifying the Clique-Width of H-Free Bipartite Graphs,
K.K. Dabrowski and D. Paulusma,
Lecture Notes in Computer Science, 8591 (2014) pp. 489-500 (Proceedings of COCOON 2014) (arXiv:1402.7060) (link)

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs,
K.K. Dabrowski, P.A. Golovach and D. Paulusma,
Lecture Notes in Computer Science, 8165 (2013) pp. 201-212 (Proceedings of WG 2013) (preprint) (link)

Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes,
K. Dabrowski, V.V. Lozin, H. Müller and D. Rautenbach,
Lecture Notes in Computer Science, 6460 (2011) pp. 1-9 (Proceedings of IWOCA 2010) (preprint) (link)

Colouring vertices of triangle-free graphs,
K. Dabrowski, V.V. Lozin, R. Raman and B. Ries,
Lecture Notes in Computer Science, 6410 (2010) pp. 184-195 (Proceedings of WG 2010) (preprint) (link)

Publications in Preparation
Colouring on Hereditary Graph Classes Closed under Complementation,
A. Blanché, K.K. Dabrowski, M. Johnson and D. Paulusma, (submitted)

On the (parameterized) complexity of recognizing well-covered (r,l)-graphs,
S.R. Alves, K.K. Dabrowski, L. Faria, S. Klein, I. Sau and U. Dos Santos Souza (submitted)

Playing with parameters: structural parameterization in graphs,
N. Bourgeois, K.K. Dabrowski, M. Demange and V. Paschos, (in preparation, arXiv:1309.6144)

Dynamic Edge-choosability
K.K. Dabrowski, in preparation (preprint available on request)

Other
Structural Solutions to Maximum Independent Set and Related Problems
K. Dabrowski, PhD Thesis (preprint) (link)

Conferences Organized

  1. I am the main organizer of the 22nd Postgraduate Combinatorial Conference 2012.
  2. I helped to organize the DIMAP Workshop on Combinatorics and Graph Theory.

Conferences/Meetings Attended

  1. 16-18 April 2009, Cambridge: Beyond Part III (participant)
  2. 12-17 July 2009, Cambridge: LMS/EPSRC Short course in Probabilistic Combinatorics (student)
  3. 10 November 2009, Oxford: Joint DIMAP-Oxford seminar (participant)
  4. 14 December 2009, Warwick: Mike's Mini-workshop on Algorithms (participant)
  5. 17 March 2010, Oxford: One-Day Meeting in Combinatorics (participant)
  6. 25-27 March 2010, Cambridge: Young Researchers in Mathematics (speaker)
  7. 6-9 April 2010, Edinburgh: 26th British Colloquium in Theoretical Computer Science (speaker)
  8. 12-16 April 2010, Warwick: European Study Group in Industry (participant)
  9. 10-11 June 2010, London: LTCC course on Synchronisation (student)
  10. 28 June - 16 July 2010, Oxford: Lecture series on Structural Graph Theory (student)
  11. 7-9 July 2010, London (Queen Mary): 21st Postgraduate Combinatorics Conference (speaker)
  12. 12-16 July 2010, Warwick: DIMAP Summer School on Approximation and Randomized Algorithms (student)
  13. 26-28 July 2010, London (King's College): 21st International Workshop on Combinatorial Algorithms (speaker)
  14. 20-22 September 2010, Durham: Algorithms and Complexity in Durham 2010 (participant)
  15. 2 February 2011, Open University: Open University Winter Combinatorics Meeting (participant)
  16. 16 March 2011, Oxford: One-Day Meeting in Combinatorics (participant)
  17. 14-16 April 2011, Warwick: Young Researchers in Mathematics (speaker)
  18. 18-21 April 2011, Birmingham: 27th British Colloquium for Theoretical Computer Science (speaker)
  19. 4-8 July 2011, Exeter: 23rd British Combinatorial Conference (speaker)
  20. 4-9 September 2011, Nový Smokovec, High Tatras, Slovakia: Workshop Cycles and Colourings (speaker)
  21. 28 September 2011, Warwick: DIMAP Retreat (speaker)
  22. 25 January 2012, Open University: Open University Winter Combinatorics Meeting (participant)
  23. 2-4 April 2012, Bristol: Young Researchers in Mathematics (speaker)
  24. 30 May 2012, Oxford: One-Day Meeting in Combinatorics (participant)
  25. 8 July 2012, Warwick: Workshop on Applications of Parameterized Algorithms and Complexity (participant)
  26. 9-13 July 2012, Warwick: International Colloquium on Automata, Languages and Programming (participant)
  27. 5-7 September 2012, Oxford: French-British Workshop on Analytic Combinatorics (participant)
  28. 9-14 September 2012, Nový Smokovec, High Tatras, Slovakia 21st Workshop Cycles and Colourings (participant)
  29. 14-15 September 2012, Nový Smokovec, High Tatras, Slovakia Hereditarnia 2012, The 15th Workshop on Hereditary Graph Properties (speaker)
  30. 13 December 2012, Durham, ACiD Seminar (speaker)
  31. 30 January 2013, Open University: Open University Winter Combinatorics Meeting (participant)
  32. 30 May - 1 June 2013, Paris (CNAM): Conference of the European Chapter on Combinatorial Optimization (participant)
  33. 4 June 2013, Paris (LIAFA): Journées Franciliennes de Recherche Opérationnelle (participant)
  34. 19-21 June 2013, Lübeck: International Workshop on Graph-Theoretic Concepts in Computer Science (speaker)
  35. 7 July 2013, Riga: International Workshop on Approximation, Parameterized and EXact algorithms (speaker)
  36. 8-12 July 2013, Riga: International Colloquium on Automata, Languages and Programming (participant)
  37. 5-9 August 2013, Saarbrücken: Advanced Course on the Foundations of Computer Science (participant)
  38. 9-14 September 2013, Nový Smokovec, High Tatras, Slovakia: 22nd Workshop Cycles and Colourings (speaker)
  39. 20 November 2013, Durham: Network Coding, Partitions and Security (participant)
  40. 23 June 2014, Durham: Computer Science Junior Seminar (speaker)
  41. 4-6 August 2014, Atlanta GA, USA: 20th International Computing and Combinatorics Conference (COCOON) (speaker)
  42. 7-12 September 2014, Nový Smokovec, High Tatras, Slovakia: 23rd Workshop Cycles and Colourings (speaker)
  43. 13-14 December 2014, New Delhi, India: New Developments in Exact Algorithms and Lower Bounds (participant)
  44. 15-17 December 2014, New Delhi, India: 34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014) (speaker)
  45. 11 February 2015, Durham: Computer Science Junior Seminar (speaker)
  46. 2-6 March 2015, Nice, France: 9th International Conference on Language and Automata Theory and Applications (LATA 2015) (speaker)
  47. 20-22 May 2015, Paris, France: 9th International Conference on Algorithms and Complexity (CIAC 2015) (speaker)
  48. 16-19 June 2015, Koper, Slovenia: Algorithmic Graph Theory on the Adriatic Coast (AGTAC 2015) (speaker)
  49. 6-10 July 2015, Warwick, UK: 25th British Combinatorial Conference (BCC 2015) (speaker)
  50. 24-28 August 2015, Milan, Italy: 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015) (speaker)
  51. 31 August - 4 September 2015, Bergen, Norway: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015) (speaker*2)
  52. 8 October 2015, Durham: Durham University School of Engineering and Computing Science Research Day (speaker)
  53. 11-15 October 2015, Aussois, France: 7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2015) (speaker)
  54. 22-24 June 2016, Reykjavik, Iceland: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) (speaker)

Links
Quotes from various people
Imre Leader Appreciation Society (mirrored from here)

Valid HTML 4.01 Strict