Click on the titles of the papers for more information, abstracts, slides and preprints. See also DBLP or Google Scholar.

Publications in scientific journals

  1. Editing to a planar graph of given degrees
    (with Konrad K. Dabrowski, Petr. A. Golovach, Daniël Paulusma and Dimitrios M. Thilokos)
    Journal of Computer and System Sciences, vol. 85, pp. 168-182, 2017

  2. The price of connectivity for feedback vertex set
    (with Rémy Belmonte, Marcin Kamiński and Daniël Paulusma)
    Discrete Applied Mathematics, vol. 217, no. 2, pp. 132-143, 2017

  3. On the computational complexity of vertex integrity and component order connectivity
    (with Pål Grønås Drange and Markus Sortland Dregi)
    Algorithmica, vol. 76, no. 4, pp. 1181-1202, 2016

  4. Maximal induced matchings in triangle-free graphs
    (with Manu Basavaraju, Pinar Heggernes, Reza Saei and Yngve Villanger)
    Journal of Graph Theory, vol. 83, no. 3, pp. 231-250, 2016

  5. Editing to Eulerian graphs
    (with Konrad K. Dabrowski, Petr A. Golovach and Daniël Paulusma)
    Journal of Computer and System Sciences, vol. 82, no. 2, pp. 213-228, 2016

  6. Hadwiger number of graphs with small chordality
    (with Petr A. Golovach, Pinar Heggernes and Christophe Paul)
    SIAM Journal on Discrete Mathematics, vol. 29, no. 3, pp. 1427-1451, 2015

  7. Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
    (with Steven Chaplick, Jiří Fiala, Daniël Paulusma and Marek Tesař)
    Theoretical Computer Science, vol. 590, pp. 86-95, 2015

  8. Induced subgraph isomorphism on proper interval and bipartite permutation graphs
    (with Pinar Heggernes, Daniel Meister and Yngve Villanger)
    Theoretical Computer Science, vol. 562, pp. 252-269, 2015

  9. Finding disjoint paths in split graphs
    (with Pinar Heggernes, Erik Jan van Leeuwen and Reza Saei)
    Theory of Computing Systems, vol. 57, no. 1, pp. 140-159, 2015

  10. Computing the metric dimension for chain graphs
    (with Henning Fernau, Pinar Heggernes, Daniel Meister and Reza Saei)
    Information Processing Letters, vol. 115, pp. 671-676, 2015

  11. Modifying a graph using vertex elimination
    (with Petr A. Golovach, Pinar Heggernes, Fredrik Manne, Daniël Paulusma and Michał Pilipczuk)
    Algorithmica, vol. 72, no. 1, pp. 99-125, 2015

  12. On the parameterized complexity of finding separators with non-hereditary properties
    (with Pinar Heggernes, Dániel Marx, Neeldhara Misra and Yngve Villanger)
    Algorithmica, vol. 72, no. 3, pp. 687-713, 2015

  13. Vector connectivity in graphs
    (with Endre Boros, Pinar Heggernes and Martin Milanič)
    Networks, vol. 64, no. 4, pp. 277-285, 2014

  14. Detecting fixed patterns in chordal graphs in polynomial time
    (with Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Marcin Kamiński and Daniël Paulusma)
    Algorithmica, vol. 69, no. 3, pp. 501-521, 2014

  15. Parameterized complexity of three edge contraction problems with degree constraints
    (with Rémy Belmonte, Petr A. Golovach and Daniël Paulusma)
    Acta Informatica, vol. 51, pp. 473-487, 2014

  16. Graph classes and Ramsey numbers
    (with Rémy Belmonte, Pinar Heggernes, Arash Rafiey and Reza Saei)
    Discrete Applied Mathematics, vol. 173, pp. 16-27, 2014

  17. Contracting graphs to paths and trees
    (with Pinar Heggernes, Benjamin Lévêque, Daniel Lokshtanov and Christophe Paul)
    Algorithmica, vol. 68, no. 1, pp. 109-132, 2014

  18. Contracting chordal graphs and bipartite graphs to paths and trees
    (with Pinar Heggernes, Benjamin Lévêque and Christophe Paul)
    Discrete Applied Mathematics, vol. 164, no. 2, pp. 444-449, 2014

  19. Characterizing graphs of small carving-width
    (with Rémy Belmonte, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos)
    Discrete Applied Mathematics, vol. 161, no. 13-14, pp. 1888-1893, 2013

  20. Exact algorithms for finding longest cycles in claw-free graphs
    (with Hajo Broersma, Fedor V. Fomin and Daniël Paulusma)
    Algorithmica, vol. 65, no. 1, pp. 129-145, 2013

  21. Minimal dominating sets in graph classes: combinatorial bounds and enumeration
    (with Jean-François Couturier, Pinar Heggernes and Dieter Kratsch)
    Theoretical Computer Science, vol. 487, pp. 82-94, 2013

  22. Choosability on H-free graphs
    (with Petr A. Golovach, Pinar Heggernes and Daniël Paulusma)
    Information Processing Letters, vol. 113, no. 4, pp. 107-110, 2013

  23. Obtaining planarity by contracting few edges
    (with Petr A. Golovach and Daniël Paulusma)
    Theoretical Computer Science, vol. 476, pp. 38-46, 2013

  24. Obtaining a bipartite graph by contracting few edges
    (with Pinar Heggernes, Daniel Lokshtanov and Christophe Paul)
    SIAM Journal on Discrete Mathematics, vol. 27, no. 4, pp. 2143-2156, 2013

  25. Parameterized complexity of vertex deletion into perfect graph classes
    (with Pinar Heggernes, Bart M. P. Jansen, Stefan Kratsch and Yngve Villanger)
    Theoretical Computer Science, vol. 511, pp. 172-180, 2013

  26. Proper interval vertex deletion
    (with Yngve Villanger)
    Algorithmica, vol. 65, no. 4, pp. 845-867, 2013

  27. Edge contractions in subclasses of chordal graphs
    (with Rémy Belmonte and Pinar Heggernes)
    Discrete Applied Mathematics, vol. 160, no. 7-8, pp. 999-1010, 2012

  28. Computing the cutwidth of bipartite permutation graphs in linear time
    (with Pinar Heggernes, Daniel Lokshtanov and Jesper Nederlof)
    SIAM Journal on Discrete Mathematics, vol. 26, no. 3, pp. 1008-1021, 2012

  29. Computing role assignments of proper interval graphs in polynomial time
    (with Pinar Heggernes and Daniël Paulusma)
    Journal of Discrete Algorithms, vol. 14, pp. 173-188, 2012

  30. Finding induced paths of given parity in claw-free graphs
    (with Marcin Kamiński and Daniël Paulusma)
    Algorithmica, vol. 62, no. 1-2, pp. 537-563, 2012

  31. On graph contractions and induced minors
    (with Marcin Kamiński, Daniël Paulusma, Stefan Szeider and Dimitrios M. Thilikos)
    Discrete Applied Mathematics, vol. 160, no. 6, pp. 799-809, 2012

  32. A new characterization of P6-free graphs
    (with Daniël Paulusma)
    Discrete Applied Mathematics, vol. 158, no. 7, pp. 731-740, 2010

  33. Computing role assignments of chordal graphs
    (with Daniël Paulusma and Johan M. M. van Rooij)
    Theoretical Computer Science, vol. 411, no. 40-42, pp. 3601-3613, 2010

  34. Constructing fair round robin tournaments with a minimum number of breaks
    (with Gerhard Post and Dirk Briskorn)
    Operations Research Letters, vol. 38, pp. 592-596, 2010

  35. Partitioning graphs into connected parts
    (with Daniël Paulusma and Gerhard J. Woeginger)
    Theoretical Computer Science, vol. 410, no. 47-49, pp. 4834-4843, 2009


Publications in refereed conference proceedings

Almost all conference papers below are superseded by journal versions; click on the titles for more info.

  1. Editing to a planar graph of given degrees
    (with Konrad K. Dabrowski, Petr. A. Golovach, Daniël Paulusma and Dimitrios M. Thilokos)
    Proceedings of CSR 2015
    Lecture Notes in Computer Science, vol. 9139, pp. 143-156, 2015

  2. Editing to Eulerian graphs
    (with Konrad K. Dabrowski, Petr A. Golovach and Daniël Paulusma)
    Proceedings of FSTTCS 2014
    Leibniz International Proceedings in Informatics (LIPIcs), vol. 29, pp. 97-108, 2014

  3. On the computational complexity of vertex integrity and component order connectivity
    (with Pål Grønås Drange and Markus Sortland Dregi)
    Proceedings of ISAAC 2014
    Lecture Notes in Computer Science, vol. 8889, pp. 285-297, 2014

  4. Maximal induced matchings in triangle-free graphs
    (with Manu Basavaraju, Pinar Heggernes, Reza Saei and Yngve Villanger)
    Proceedings of WG 2014
    Lecture Notes in Computer Science, vol. 8747, pp. 93-104, 2014

  5. Hadwiger number of graphs with small chordality
    (with Petr A. Golovach, Pinar Heggernes and Christophe Paul)
    Proceedings of WG 2014
    Lecture Notes in Computer Science, vol. 8747, pp. 201-213, 2014

  6. Forbidden induced subgraphs and the price of connectivity for feedback vertex set
    (with Rémy Belmonte, Marcin Kamiński and Daniël Paulusma)
    Proceedings of MFCS 2014
    Lecture Notes in Computer Science, vol. 8635, pp. 57-68, 2014

  7. Finding disjoint paths in split graphs
    (with Pinar Heggernes, Erik Jan van Leeuwen and Reza Saei)
    Proceedings of SOFSEM 2014
    Lecture Notes in Computer Science, vol. 8327, pp. 315-326, 2014

  8. Induced subtrees in interval graphs
    (with Pinar Heggernes and Martin Milanič)
    Proceedings of IWOCA 2013
    Lecture Notes in Computer Science, vol. 8288, pp. 230-243, 2013

  9. Parameterized complexity of two edge contraction problems with degree constraints
    (with Rémy Belmonte, Petr A. Golovach and Daniël Paulusma)
    Proceedings of IPEC 2013
    Lecture Notes in Computer Science, vol. 8246, pp. 16-27, 2013

  10. The price of connectivity for feedback vertex set
    (with Rémy Belmonte, Marcin Kamiński and Daniël Paulusma)
    Proceedings of Eurocomb 2013
    CRM Series, vol. 16, pp. 123-128, 2013

  11. Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
    (with Steven Chaplick, Jiří Fiala, Daniël Paulusma and Marek Tesař)
    Proceedings of FCT 2013
    Lecture Notes in Computer Science, vol. 8070, pp. 121-132, 2013

  12. Vector connectivity in graphs
    (with Endre Boros, Pinar Heggernes and Martin Milanič)
    Proceedings of TAMC 2013
    Lecture Notes in Computer Science, vol. 7876, pp. 331-342, 2013

  13. Induced immersions
    (with Rémy Belmonte and Marcin Kamiński)
    Proceedings of ISAAC 2012
    Lecture Notes in Computer Science, vol. 7676, pp. 299-308, 2012

  14. How to eliminate a graph
    (with Petr A. Golovach, Pinar Heggernes, Fredrik Manne, Daniël Paulusma and Michał Pilipczuk)
    Proceedings of WG 2012
    Lecture Notes in Computer Science, vol. 7551, pp. 320-331, 2012

  15. On the parameterized complexity of finding separators with non-hereditary properties
    (with Pinar Heggernes, Dániel Marx, Neeldhara Misra and Yngve Villanger)
    Proceedings of WG 2012
    Lecture Notes in Computer Science, vol. 7551, pp. 332-343, 2012

  16. Ramsey numbers for line graphs and perfect graphs
    (with Rémy Belmonte, Pinar Heggernes and Reza Saei)
    Proceedings of COCOON 2012 (best paper award)
    Lecture Notes in Computer Science, vol. 7434, pp. 204-215, 2012

  17. Maximum number of minimal feedback vertex sets in chordal graphs and cographs
    (with Jean-François Couturier, Pinar Heggernes and Yngve Villanger)
    Proceedings of COCOON 2012
    Lecture Notes in Computer Science, vol. 7434, pp. 133-144, 2012

  18. Characterizing graphs of small carving-width
    (with Rémy Belmonte, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos)
    Proceedings of COCOA 2012
    Lecture Notes in Computer Science, vol. 7402, pp. 360-370, 2012

  19. Obtaining planarity by contracting few edges
    (with Petr A. Golovach and Daniël Paulusma)
    Proceedings of MFCS 2012
    Lecture Notes in Computer Science, vol. 7464, pp. 455-466, 2012

  20. Computing minimum geodetic sets of proper interval graphs
    (with Tınaz Ekim, Aysel Erey, Pinar Heggernes and Daniel Meister)
    Proceedings of LATIN 2012
    Lecture Notes in Computer Science, vol. 7256, pp. 279-290, 2012

  21. Minimal dominating sets in graph classes: combinatorial bounds and enumeration
    (with Jean-François Couturier, Pinar Heggernes and Dieter Kratsch)
    Proceedings of SOFSEM 2012
    Lecture Notes in Computer Science, vol. 7147, pp. 202-213, 2012

  22. Contracting graphs to paths and trees
    (with Pinar Heggernes, Benjamin Lévêque, Daniel Lokshtanov and Christophe Paul)
    Proceedings of IPEC 2011
    Lecture Notes in Computer Science, vol. 7112, pp. 55-66, 2012

  23. Finding contractions and induced minors in chordal graphs via disjoint paths
    (with Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Marcin Kamiński and Daniël Paulusma)
    Proceedings of ISAAC 2011
    Lecture Notes in Computer Science, vol. 7074, pp. 110-119, 2011

  24. Obtaining a bipartite graph by contracting few edges
    (with Pinar Heggernes, Daniel Lokshtanov and Christophe Paul)
    Proceedings of FSTTCS 2011
    Leibniz International Proceedings in Informatics (LIPIcs), vol. 13, pp. 217-228, 2011

  25. Parameterized complexity of vertex deletion into perfect graph classes
    (with Pinar Heggernes, Bart M. P. Jansen, Stefan Kratsch and Yngve Villanger)
    Proceedings of FCT 2011
    Lecture Notes in Computer Science, vol. 6914, pp. 240-251, 2011

  26. Edge contractions in subclasses of chordal graphs
    (with Rémy Belmonte and Pinar Heggernes)
    Proceedings of TAMC 2011
    Lecture Notes in Computer Science, vol. 6648, pp. 528-539, 2011

  27. Contracting chordal graphs and bipartite graphs to paths and trees
    (with Pinar Heggernes, Benjamin Lévêque and Christophe Paul)
    Proceedings of LAGOS 2011
    Electronic Notes in Discrete Mathematics, vol. 37, pp. 87-92, 2011

  28. Computing role assignments of proper interval graphs in polynomial time
    (with Pinar Heggernes and Daniël Paulusma)
    Proceedings of IWOCA 2010
    Lecture Notes in Computer Science, vol. 6460, pp. 167-180, 2011

  29. Computing the cutwidth of bipartite permutation graphs in linear time
    (with Pinar Heggernes, Daniel Lokshtanov and Jesper Nederlof)
    Proceedings of WG 2010
    Lecture Notes in Computer Science, vol. 6410, pp. 75-87, 2010

  30. On contracting graphs to fixed pattern graphs
    (with Marcin Kamiński, Daniël Paulusma, Stefan Szeider and Dimitrios M. Thilikos)
    Proceedings of SOFSEM 2010
    Lecture Notes in Computer Science, vol. 5901, pp. 503-514, 2010

  31. Fast exact algorithms for hamiltonicity in claw-free graphs
    (with Hajo Broersma, Fedor V. Fomin and Daniël Paulusma)
    Proceedings of WG 2009
    Lecture Notes in Computer Science, vol. 5911, pp. 44-53, 2009

  32. Finding induced paths of given parity in claw-free graphs
    (with Marcin Kamiński and Daniël Paulusma)
    Proceedings of WG 2009
    Lecture Notes in Computer Science, vol. 5911, pp. 341-352, 2009

  33. Computing role assignments of chordal graphs
    (with Daniël Paulusma and Johan M. M. van Rooij)
    Proceedings of FCT 2009
    Lecture Notes in Computer Science, vol. 5699, pp. 193-204, 2009

  34. Partitioning graphs into connected parts
    (with Daniël Paulusma and Gerhard J. Woeginger)
    Proceedings of CSR 2009
    Lecture Notes in Computer Science, vol. 5675, pp. 143-154, 2009

  35. A new characterization of P6-free graphs
    (with Daniël Paulusma)
    Proceedings of COCOON 2008
    Lecture Notes in Computer Science, vol. 5092, pp. 415-424, 2008

Theses

  1. Exploiting structure to cope with NP-hard graph problems: Polynomial and exponential time exact algorithms
    PhD thesis, Durham University, UK, 2010.

  2. On 3-coloring of planar and smooth graphs
    MSc thesis, University of Twente, the Netherlands, 2006