Staff profile
Overview
https://www.dur.ac.uk/images/ECS_IMAGES/Staff/PaulusmaDan.jpg
Professor Daniel Paulusma
Professor
MSc PhD
| Affiliation | Room number | Telephone |
|---|---|---|
| Professor in the Department of Computer Science | MCS 2064 | +44 (0) 191 33 41723 |
Research groups
- Algorithms and Complexity
Publications
Chapter in book
Conference Paper
- Berthe, G., Martin, B., Paulusma, D. & Smith, S. (2022), The Complexity of L(p,q)-Edge-Labelling, Lecture Notes in Computer Science The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021). University of Jember, East Java, Springer.
- Benedek, M., Biro, P., Kern, W. & Paulusma, D. (2022), Computing balanced solutions for large international kidney exchange schemes, AAMAS 2022.
- Paesani, G., Paulusma, D. & Rzążewski, P. (2021), Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs, in Bonchi, Filippo & Puglisi, Simon J. eds, Leibniz International Proceedings in Informatics 202: MFCS 2021. Tallinn, Estonia, Dagstuhl, 1-14.
- Brettell, N., Johnson, M. & Paulusma, D. (2021), Computing weighted subset transversals in H-free graphs, Lecture Notes in Computer Science WADS 2021. Halifax, Nova Scotia, Springer.
- Brause, C., Golovach, P.A., Martin, B., Paulusma, D. & Smith, S. (2021), Partitioning H-free graphs of bounded diameter, Leibniz International Proceedings in Informatics ISAAC 2021. Fukuoka / Online, Schloss Dagstuhl.
- Brause, C., Golovach P.A., Martin, B., Paulusma, D. & Smith, S. (2021), Acyclic, star and injective colouring: bounding the diameter, Lecture Notes in Computer Science WG 2021. Virtual, Springer.
- Bonomo-Braberman, F., Brettell, N., Munaro, A. & Paulusma, D. (2021), Solving problems on generalized convex graphs via mim-width, Lecture Notes in Computer Science WADS 2021. Halifax, Nova Scotia, Springer.
- Larose, B., Markovic, P. Martin, B., Paulusma, D., Smith, S. & Zivny, S. (2021), QCSP on reflexive tournaments, in Mutzel, Petra, Pagh, Rasmus & Herman, Grzegorz eds, Leibniz International Proceedings in Informatics The 29th Annual European Symposium on Algorithms (ESA 2021). Lisbon / Online, Dagstuhl.
- Kern, W., Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E.J. (2021), Disjoint paths and connected subgraphs for H-free graphs, Lecture Notes in Computer Science IWOCA 2021. Online, Springer.
- Bok, J., Jedličková, N., Martin, B., Paulusma, D. & Smith, S. (2021), Injective colouring for H-free graphs, Lecture Notes in Computer Science CSR 2021. Sochi, Springer.
- Martin, B., Paulusma, D. & Smith, S. (2021), Colouring graphs of bounded diameter in the absence of small cycles, Lecture Notes in Computer Science CIAC 2021. Springer.
- Kern, W. & Paulusma, D. (2020), Contracting to a longest path in H-free graphs, in Cao, Y., Cheng, S. & Li, M. eds, Leibniz International Proceedings in Informatics 181: ISAAC 2020. Hong Kong, China, Schloss Dagstuhl, 22:1-22:18
- Brettell, N. Horsfield, J. Munaro, A. Paesani, G. & Paulusma, D. (2020), Bounding the mim-width of hereditary graph classes, in Cao, Y. & Pilipczuk, M. eds, Leibniz International Proceedings in Informatics 12301: IPEC 2020. Schloss Dagstuhl, 187-199.
- Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D. & van Leeuwen, E.J. (2020), Steiner trees for hereditary graph classes, in Kohayakawa, Y. & Miyazawa, F.K. eds, Lecture Notes in Computer Science 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings: LATIN 2020. São Paulo, Springer, 613-624.
- Dabrowski, K.K., Masařík, T., Novotná, J., Paulusma, D. & Rzążewski, P. (2020), Clique-Width: Harnessing the Power of Atoms, in Adler, I. & Müller, H. eds, Lecture Notes in Computer Science 12301: WG 2020. Leeds, England, Springer, Cham, 119-133.
- Brettell, N., Johnson, M., Paesani, G. & Paulusma, D. (2020), Computing subset transversals in H-free graphs, in Adler, I. & Müller, H. eds, Lecture Notes in Computer Science 12301: WG 2020. Leeds, England, Springer, 187-199.
- Bok, J., Jedlickova, N., Martin, B., Paulusma, D. & Smith, S. (2020), Acyclic, star and injective colouring: a complexity picture for H-free graphs, Leibniz International Proceedings in Informatics ESA 2020. Schloss Dagstuhl.
- Martin, B. Paulusma, D. & Smith, S. (2019), Colouring H-free graphs of bounded diameter, in Rossmanith, Peter Heggernes, Pinar & Katoen, Joost-Pieter eds, Leibniz International Proceedings in Informatics MFCS 2019. Aachen, Germany, 14:1–14:14.
- Dabrowski, K.K. Dross, F. Jeong, J. Kanté, M.M. Kwon, O. Oum, S. & Paulusma, D. (2019), Tree pivot-minors and linear rank-width, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 577-583.
- Dabrowski, K.K., Johnson, M., Paesani, G. Paulusma, D. & Zamaraev, V. (2019), Independent transversals versus transversals, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 585-591.
- Bonamy, M., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019), Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy, in Friggstad, Zachary Sack, Jörg-Rüdiger & Salavatipour, Mohammad R. eds, Lecture Notes in Computer Science 11646: WADS 2019. Edmonton, Canada, Springer, Cham, 181-195.
- Feghali, C. Johnson, M., Paesani, G. & Paulusma, D. (2019), On cycle transversals and their connected variants in the absence of a small linear forest, in Gąsieniec, Leszek Antoni Jansson, Jesper & Levcopoulos, Christos eds, Lecture Notes in Computer Science 11651: FCT 2019. Copenhagen, Denmark, Springer, Cham, 258-273.
- Bulteau, L. Dabrowski, K.K. Fertin, G., Johnson, M. Paulusma, D. & Vialette S. (2019), Finding a small number of colourful components, Leibniz International Proceedings in Informatics CPM 2019. Pisa, Italy, Schloss Dagstuhl, Saarbrücken, Germany.
- Biro, P., Kern, W., Palvolgyi, D. & Paulusma, D. (2019), Generalized matching games for international kidney exchange, AAMAS 2019. Montreal, Canada, Association for Computing Machinery (ACM).
- Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D. & Slívová, V. (2018), Colouring (Pr+Ps)-free graphs, in Hsu, Wen-Lian, Lee, Der-Tsai & Liao, Chung-Shou eds, Leibniz International Proceedings in Informatics 123: 29th International Symposium on Algorithms and Computation (ISAAC 2018). Jiaoxi, Yilan County, Taiwan, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 5:1--5:13.
- Johnson, M., Paesani, G. & Paulusma, D. (2018), Connected Vertex Cover for (sP1+P5)-free graphs, in Brandstädt, Andreas, Köhler, Ekkehard & Meer, Klaus eds, Lecture Notes in Computer Science, 11159 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018). Cottbus, Germany, Springer, Cham, 279-291.
- Dabrowski, K.K., Dross, F., Jeong, J., Kanté, M.M., Kwon, O., Oum, S. & Paulusma, D. (2018), Computing small pivot-minors, in Brandstädt, A., Köhler, E. & Meer, K. eds, Lecture Notes in Computer Science 11159: 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018). Cottbus, Germany, Springer, Cham, Switzerland, 125-138.
- Hof, F., Kern, W., Kurz, S. & Paulusma, D. (2018), Simple games versus weighted voting games, in Deng, Xiaotie eds, Lecture Notes in Computer Science, 11059 11th International Symposium on Algorithmic Game Theory (SAGT 2018). Beijing, China, Springer, Cham, 69-81.
- Larose, B., Martin, B. & Paulusma, D. (2018), Surjective H-Colouring over Reflexive Digraphs, in Niedermeier, Rolf & Vallée, Brigitte eds, Leibniz International Proceedings in Informatics (LIPIcs) 96: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Caen, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 49:1-49:14.
- Dabrowski, K.K., Johnson, M., Paesani, G., Paulusma, D. & Zamaraev, V. (2018), On the price of independence for vertex cover, feedback vertex set and odd cycle transversal, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics 117: 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 63:1--63:15.
- Martin, B., Paulusma, D. & van Leeuwen, E.J. (2018), Disconnected Cuts in Claw-free Graphs, in Azar, Yossi, Bast, Hannah & Herman, Grzegorz eds, Leibniz International Proceedings in Informatics (LIPIcs) 112: 26th Annual European Symposium on Algorithms (ESA 2018). Helsinki, Finland., Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 61:1--61:14.
- Gaspers, S., Huang, S. & Paulusma, D. (2018), Colouring Square-Free Graphs without Long Induced Paths, in Niedermeier, Rolf & Vallée, Brigitte eds, Leibniz International Proceedings in Informatics (LIPIcs) 96: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Caen, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 35:1-35:15.
- Dabrowski, K.K., Lozin, V.V. & Paulusma, D. (2017), Clique-width and well-quasi ordering of triangle-free graph classes, in Bodlaender, Hans L. & Woeginger, Gerhard J. eds, Lecture Notes in Computer Science 10520: WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science. Eindhoven, The Netherlands, Springer, Cham, 220-233.
- Golovach, P.A., Heggernes, P., Kratsch, D., Lima, P.T. & Paulusma, D. (2017), Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, in Bodlaender, Hans L. & Woeginger, Gerhard J. eds, Lecture Notes in Computer Science 10520: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017). Eindhoven, Springer, Cham, 275-288.
- Picouleau, C., Paulusma, D. & Ries, B. (2017), Reducing the chromatic number by vertex or edge deletions, Electronic Notes in Discrete Mathematics 62: LAGOS 2017. Marseille, France, 243-248.
- Dabrowski, K.K. & Paulusma, D. (2017), Contracting bipartite graphs to paths and cycles, Electronic Notes in Discrete Mathematics 61: Eurocomb 2017: European Conference on Combinatorics, Graph Theory and Applications. Vienna, Elsevier, 309-315.
- Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2017), Recognizing Graphs Close to Bipartite Graphs, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 70.
- Golovach, P. A., Johnson, M., Martin, M., Paulusma, D. & Stewart, A. (2017), Surjective H-Colouring: new hardness results, in Kari J., Manea F. & Petre I. eds, Lecture Notes in Computer Science 10307: Computability in Europe (CiE 2017). Turku, Finland, Springer, Cham, 270-281.
- Paulusma, D., Picouleau, C. & Ries, B. (2017), Blocking independent sets for H-free graphs via edge contractions and vertex deletions, in Gopal, T., Jäger, G. & Steila, S. eds, Lecture Notes in Computer Science 10185: Theory and applications of models of computation, 14th Annual Conference, TAMC 2017. Bern, Switzerland, Springer, Cham, 470-483.
- Blanché, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D. & Zamaraev, V. (2017), Clique-Width for Graph Classes Closed under Complementation, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 73.
- Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2017), Independent Feedback Vertex Set for P5-free Graphs, in Okamoto, Yoshio & Tokuyama, Takeshi eds, Leibniz International Proceedings in Informatics 92: ISAAC 2017. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1-16:12.
- Golovach, P.A., Kratsch, D., Paulusma, D. & Stewart, A. (2016), Squares of low clique number, Electronic Notes in Discrete Mathematics 55: 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16). Gargnano, Elsevier, 195-198.
- Paulusma, D., Picouleau, C. & Ries, B. (2016), Reducing the clique and chromatic number via edge contractions and vertex deletions, in Cerulli, Raffaele, Fujishige, Satoru & Mahjoub, A. Ridha eds, Lecture Notes in Computer Science, 9849 9849: 4th International Symposium on Combinatorial Optimization (ISCO 2016). Vietri sul Mare, Italy, Springer, Cham, Switzerland, 38-49.
- Dabrowski, K.K., Lozin, V.V. & Paulusma, D. (2016), Well-quasi-ordering versus clique-width: new results on bigenic classes, in Mäkinen, Veli, Puglisi, Simon J. & Salmela, Leena eds, Lecture Notes in Computer Science 9843: 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). Helsinki, Finland, Springer, Cham, Switzerland, 253-265.
- Golovach, P.A., Kratsch, D., Paulusma, D. & Stewart, A. (2016), Finding cactus roots in polynomial time, in Mäkinen, Veli, Puglisi, Simon J. & Salmela, Leena eds, Lecture Notes in Computer Science 9843: 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). Helsinki, Finland, Springer, Cham, Switzerland, 361-372.
- Biró, P., Kern, W., Paulusma, D. & Wojuteczky, P. (2016), The stable fixtures problem with payments, in Mayr, Ernst W. eds, Lecture Notes in Computer Science, 9224 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015). Munich, Germany, Springer, Berlin, 49-63.
- Paulusma, D. (2016), Open problems on graph coloring for special graph classes, in Mayr, Ernst W. eds, Lecture Notes in Computer Science, 9224 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015). Munich, Germany, Springer, Berlin, 16-30.
- Dabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2016), Filling the complexity gaps for colouring planar and bounded degree graphs, in Lipták, Zsuzsanna & Smyth, William F. eds, Lecture Notes in Computer Science 9538: 26th International Workshop on Combinatorial Algorithms (IWOCA 2015). Verona, Italy, Springer, 100-111.
- Bonsma, P. & Paulusma, D. (2016), Using contracted solution graphs for solving reconfiguration problems, in Faliszewski, P., Muscholl, A. & Niedermeier, R. eds, Leibniz International Proceedings in Informatics (LIPIcs) 58: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Krakow, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Dagstuhl, 20.
- Golovach, P.A., Kratsch, D., Paulusma, D. & Stewart, A. (2016), A linear kernel for finding square roots of almost planar graphs, in Pagh, Rasmus eds, Leibniz International Proceedings in Informatics (LIPIcs) 53: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Reykjavik, Iceland, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 4.
- Dabrowski, K.K., Dross, F. & Paulusma, D. (2016), Colouring diamond-free graphs, in Pagh, Rasmus eds, Leibniz International Proceedings in Informatics (LIPIcs) 53: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Reykjavik, Iceland, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, 16.
- Feghali, C., Johnson, M. & Paulusma, D. (2015), Kempe equivalence of colourings of cubic graphs, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Bergen, 243-249.
- Dabrowski, K.K., Golovach, P.A., van 't Hof, P., Paulusma, D. & Thilikos, D.M. (2015), Editing to a planar graph of given degrees, Lecture Notes in Computer Science 9139: Springer, 143-156.
- Brandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2015), Bounding the Clique-Width of H-free Chordal Graphs, Lecture Notes in Computer Science 9235: 40th International Symposium, MFCS 2015. Milan, Italy, Springer, Milan, 139-150.
- Dabrowski, K.K. & Paulusma, D. (2015), Clique-width of graph classes defined by two forbidden induced subgraphs, in Paschos, Vangelis Th. & Widmayer, Peter eds, Lecture Notes in Computer Science 9079: 9th International Conference on Algorithms and Complexity (CIAC 2015). Paris, France, Springer, Paris, 167-181.
- Dabrowski, K.K., Huang, S. & Paulusma, D. (2015), Bounding clique-width via perfect graphs, in Dediu, Adrian-Horia, Formenti, Enrico, Martín-Vide, Carlos & Truthe, Bianca eds, Lecture Notes in Computer Science 8977: International Conference on Language and Automata Theory and Applications. Nice, France, Springer, Nice, 676-688.
- Hartinger, T.R., Johnson, M., Milanič, M. & Paulusma, D. (2015), The price of connectivity for cycle transversals, Lecture Notes in Computer Science 9235: 40th International Symposium, MFCS 2015. Milan, Italy, Springer, Milan, 395-406.
- Diner, Ö., Paulusma, D., Picouleau, C. & Ries, B. (2015), Contraction blockers for graphs with forbidden induced paths, in Paschos, Vangelis Th. & Widmayer, Peter eds, Lecture Notes in Computer Science 9079: 9th International Conference on Algorithms and Complexity (CIAC 2015). Paris, France, Springer, Paris, 194-207.
- Brandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2015), Bounding the clique-width of H-free split graphs, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Elsevier, Bergen, 497-503.
- Johnson, M., van Leeuwen, E.J. & Paulusma, D. (2015), What graphs are 2-dot product graphs?, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Elsevier, Bergen, 705-711.
- Kamiński, M., Paulusma, D., Stewart, A. & Thilikos, D.M. (2015), Minimal disconnected cuts in planar graphs, in Kosowski, A. & Walukiewicz, I. eds, Lecture Notes in Computer Science 9210: 20th International Symposium, FCT 2015. Gdańsk, Poland, Springer, Gdansk, 243-254.
- Belmonte, R., Hof, van 't P., Kaminski, M. & Paulusma D. (2014), Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set, in Csuhaj-Varjú, Ersébet, Dietzfelbinger, Martin & Ésik, Zoltán eds, Lecture notes in computer science 8635: 39th International Symposium, MFCS 2014. Budapest, Hungary, Springer, Budapest, 57-68.
- Feghali, C., Johnson, M. & Paulusma, D. (2014), A Reconfigurations Analogue of Brooks’ Theorem, in Csuhaj-Varjú, Ersébet, Dietzfelbinger, Martin & Ésik, Zoltán eds, Lecture notes in computer science 8635: 39th International Symposium, MFCS 2014. Budapest, Hungary, Springer, Budapest, 287-298.
- Dabrowski, K.K., Golovach, P.A., Hof, van 't P. & Paulusma, D. (2014), Editing to Eulerian Graphs, in Raman, Venkatesh & Suresh, S. P. eds, Leibniz International Proceedings in Informatics (LIPIcs) 29: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Budapest, Hungary, Schloss Dagstuhl, Budapest, 97-108.
- Johnson, M., Kratsch, D., Kratsch, S., Patel, V. & Paulusma, D. (2014), Finding Shortest Paths Between Graph Colourings, in Cygan, Marek & Heggernes, Pinar eds, Lecture notes in computer science 8894: 9th International Symposium, IPEC 2014. Wroclaw, Poland, Springer, Wroclaw, 221-233.
- Dabrowski, K.K. & Paulusma, D. (2014), Classifying the Clique-Width of H-Free Bipartite Graphs, in Cai, Zhipeng, Zelikovsky, Alexander & Bourgeois, Anu G. eds, Lecture Notes in Computer Science 8591: 20th International Conference, COCOON 2014. Atlanta, GA, USA, Springer, Atlanta GA, 489-500.
- Johnson, M., Paulusma, D. & Stewart, A. (2014), Knocking Out P_k-free Graphs, in Csuhaj-Varjú, Ersébet, Dietzfelbinger, Martin & Ésik, Zoltán eds, Lecture Notes in Computer Science 8635: 39th International Symposium, MFCS 2014. Budapest, Hungary, Springer, Budapest, 396-407.
- Huang, S., Johnson, M. & Paulusma, D. (2014), Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs, in Gu, Qianping, Hell, Pavol & Yang, Boting eds, Lecture Notes in Computer Science 8546: 10th International Conference, AAIM 2014. Vancouver, BC, Canada, Springer, Vancouver, British Columbia, 162-173.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2014), Induced Disjoint Paths in Circular-Arc Graphs in Linear Time, Lecture notes in computer science 8747: 40th International Workshop, WG 2014. Nouan-le-Fuzelier, France, Springer, Nouan-le-Fuzelier, 225-237.
- Golovach, P., Paulusma, D. & Stewart, I.A. (2013), Graph editing to a fixed target, in Lecroq, T. & Mouchard, L. eds, Lecture Notes in Computer Science 8288: International Workshop on Combinatorial Algorithms. Rouen, France, Springer, Rouen, 192-205.
- Belmonte, R., Hof, van 't P., Kaminski, M. & Paulusma, D. (2013), The price of connectivity for feedback vertex set, in Nešetřil, Jaroslav & Pellegrini, Marco eds, Publications of the Scuola Normale Superiore 16: 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013. Pisa, Italy, Scuola Normale Superiore, Pisa, 123-128.
- Paulusma, D., Slivovksy, F. & Szeider, S. (2013), Model counting for CNF formuals of bounded module treewidth, in Natacha Portier, & Thomas Wilke eds, Leibniz International Proceedings in Informatics (LIPIcs) 20: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Kiel, Christian-Albrechts-Universität zu Kiel, Germany, Schloss Dagstuhl, Christian-Albrechts-Universitt zu Kiel, 55--66.
- Cochefert, M., Couturier, J-F., Golovach, P.A., Kratsch, D. & Paulusma, D. (2013), Sparse Square Roots, in Brandstädt, Andreas, Jansen, Klaus & Reischuk, Rüdiger eds, Lecture Notes in Computer Science 8165: 39th International Workshop, WG 2013. Lübeck, Germany, Springer, Lbeck, 177-188.
- Johnson, M., Paulusma, D. & van Leeuwen, E.J. (2013), Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs, in Cai, Leizhen, Cheng, Siu-Wing & Lam, Tak-Wah eds, Lecture Notes in Computer Science 8283: 24th International Symposium, ISAAC 2013. Hong Kong, China, Springer, Hong Kong, 130-140.
- Chaplick, S., Fiala, J., Hof, van 't P., Paulusma, D. & Tesar, M. (2013), Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree, in Gąsieniec, Leszek & Wolter, Frank eds, Lecture Notes in Computer Science 8070: 19th International Symposium, FCT 2013. Liverpool, Springer, Berlin, Heidelberg, 121-132.
- Dabrowski, K.K., Golovach, P.A. & Paulusma, D. (2013), Colouring of Graphs with Ramsey-Type Forbidden Subgraphs, in Brandstädt, Andreas, Jansen, Klaus, & Reischuk, Rüdiger eds, Lecture Notes in Computer Science 8165: 39th International Workshop, WG 2013. Lübeck, Germany, Springer, Lbeck, 201-212.
- Golovach, P.A. & Paulusma, D. (2013), List Coloring in the Absence of Two Subgraphs, in Spirakis, Paul G. & Serna, Maria eds, Lecture Notes in Computer Science 7878: 8th International Conference, CIAC 2013. Barcelona, Spain, Springer, Barcelona, 288-299.
- Broersma, H.J., Fiala, J., Golovach, P.A., Kaiser, T., Paulusma, D. & Proskurowski, A. (2013), Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs, in Brandstädt, Andreas, Jansen, Klaus & Reischuk, Rüdige eds, Lecture Notes in Computer Science 8165: 39th International Workshop, WG 2013. Lübeck, Springer, Berlin, Heidelberg, 127-138.
- Belmonte, R., Golovach, P.A., Hof, van 't P. & Paulusma, D. (2013), Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints, Lecture Notes in Computer Science 8246: 8th International Symposium, IPEC 2013. Sophia Antipolis, France, Springer, Sophia Antipolis, 16-27.
- Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2012), Characterizing graphs of small carving-width, in Guohui Lin eds, 7402: Springer, 360-370.
- Golovach, P.A., Paulusma, D. & Ries, B. (2012), Coloring graphs characterized by a forbidden subgraph, in Branislav Rovan, Vladimiro Sassone, & Peter Widmayer eds, 7464: Springer, 443-454
- Golovach, P.A., Paulusma, D. & Song, J. (2012), 4-Coloring H-free graphs when H is small, in Mária Bieliková, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser, & György Turán eds, 7147: Springer, 289-300.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2012), Induced disjoint paths in AT-free graphs, in Fedor V. Fomin, & Petteri Kaski eds, 7357: Springer, 153-164.
- Golovach, P.A., Lidicky, B., Martin, B. & Paulusma, D. (2012), Finding vertex-surjective graph homomorphisms, in Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö, & Michail Prilutskii eds, 7353: Springer, 160-171.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2012), Induced disjoint paths in claw-free graphs, in Leah Epstein, & Paolo Ferragina eds, 7501: Springer, 515-526.
- Golovach, P.A., van 't Hog, P. & Paulusma, D. (2012), Obtaining planarity by contracting few edges, in Branislav Rovan, Vladimiro Sassone, & Peter Widmayer eds, 7464: Springer, 455-466.
- Golovach, P.A., Paulusma, D. & Song, J. (2012), Closing complexity gaps for coloring problems on H-free graphs, in Kun-Mao Chao, Tsan-sheng Hsu, & Der-Tsai Lee eds, 7676: Springer, 14-23.
- Golovach, P.A, Kratsch, D. & Paulusma, D. (2012), Detecting induced minors in AT-free graphs, in Kun-Mao Chao, Tsan-sheng Hsu, & Der-Tsai Lee eds, 7676: Springer, 495-505.
- Golovach, P.A., Heggernes, P., van 't Hof, P., Manne, F., Paulusma, D. & Pilipczuk, M. (2012), How to eliminate a graph, in Martin Charles Golumbic, Michal Stern, Avivit Levy, & Gila Morgenstern eds, 7551: Springer, 320-331
- Biró, P., Bomhoff, M., Golovach, P.A., Kern, W. & Paulusma, D. (2012), Solutions for the stable rommates problem with payments, in Martin Charles Golumbic, Michal Stern, Avivit Levy, & Gila Morgenstern eds, 7551: Springer, 69-80
- Ordyniak, S., Paulusma, D. & Szeider, S. (2011), Satisfiability of acyclic and almost acyclic CNF formulas (II), in Sakallah, K.A. & Simons, L. eds, Lecture notes in computer science 6695: 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011. Ann Arbor, MI, Springer, Ann Arbor MI, 47-60.
- Martin, B. & Paulusma, D. (2011), The computational complexity of Disconnected Cut and 2K2-Partition, in Lee, Jimmy eds, Lecture Notes in Computer Science 6876: Principles and Practice of Constraint Programming, 17th International Conference, CP 2011. Perugia, Italy, Springer, Perugia, 561-575.
- Heggernes, P., Hof, van 't P. & Paulusma, D. (2011), Computing Role Assignments of Proper Interval Graphs in Polynomial Time, in Iliopoulos, Costas S. & Smyth, William F. eds, Lecture Notes in Computer Science 6460: 21st International Workshop on Combinatorial Algorithms, IWOCA 2010. London, Springer, Berlin; Heidelberg, 167-180.
- Golovach, P.A., Paulusma, D. & Song, J. (2011), Computing vertex-surjective homomorphisms to partially reflexive trees, in Kulikov, A. & Vereshchagin, N. eds, Lecture notes in computer science 6651: 6th International Computer Science Symposium in Russia, CSR 2011. St Petersburg, Russia, Springer, St Petersburg, 261-274.
- Golovach, P.A., Paulusma, D. & Song, J. (2011), Coloring graphs without short cycles and long induced paths, in Owe, O., Steffen, M. & Telle, J.A. eds, Lecture Notes in Computer Science 6914: Fundamentals of Computation Theory, 18th International Symposium, FCT 2011. Oslo, Norway, Springer, Oslo, 193-204.
- Belmonte, R., Golovach, P.A., Heggernes, P., Hof van 't, P., Kaminski, M. & Paulusma, D. (2011), Finding contractions and induced minors in chordal graphs via disjoint paths, in Asano, T., Nakano, S., Okamoto, Y. & Watanabe. O. eds, Lecture notes in computer science 7074: 22nd International Symposium on Algorithms and Computation, ISAAC 2011. Yokohama, Japan, Springer, Yokohama, 110-119.
- Couturier, J.F., Golovach, P.A., Kratsch, D. & Paulusma, D. (2011), List coloring in the absence of a linear forest, in Kolman, P. & Kratochvil, J. eds, Lecture notes in computer science 6986: 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011. Tepla Monastery, Czech Republic, Springer, Tepla Monastery, 119-130.
- Golovach, P.A., Kamiński, M., Paulusma, D. & Thilikos, D.M. (2011), Lift Contractions, 38: Elsevier, 407-412.
- Golovach, P.A., Kaminski, M. & Paulusma, D. (2011), Contracting a chordal graph to a split graph or a tree, in Murlak, F. & Sankowski, P. eds, Lecture notes in computer science 6907: 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011. Warsaw, Poland, Springer, Warsaw, 339-350.
- Bonamy, M., Johnson, M., Lignos, I.M., Patel, V. & Paulusma, D. (2011), On the diameter of reconfiguration graphs for vertex colourings, 38: Elsevier, 161-166.
- Golovach, P.A., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2011), Increasing the Minimum Degree of a Graph by Contractions, 7112: 67-79.
- Golovach, P.A., Lidicky, B. & Paulusma, D. (2010), L(2,1,1)-labeling is NP-complete for trees, in Kratochvíl, Jan Li, Angsheng Fiala, Jirí & Kolman, Petr eds, Lecture Notes in Computer Science 6108: 7th Annual Conference on Theory and Applications of Models of Computation. Prague, Czech Republic, Springer, Prague, 211-221.
- Johnson, M., Paulusma, D. & Wood, C. (2010), Path factors and parallel knock-out schemes of almost claw-free graphs, in Miller, Mirka & Wada, Koichi eds, 19th International Workshop on Combinatorial Algorithms. Nagoya, College Publications, 27-41.
- Fiala, J., Kaminski, M., Lidicky, B. & Paulusma, D. (2010), The k-in-a-path problem for claw-free graphs, in Marion, Jean-Yves & Thomas, Schwentick eds, Leibniz International Proceedings in Informatics 5: 27th International Symposium on Theoretical Aspects of Computer Science. Nancy, France, Dagstuhl, Nancy, 371-382
- Broersma, H.J., Golovach, P.A., Paulusma, D. & Song, J. (2010), On Coloring Graphs without Induced Forests, 6507: 156-167.
- Johnson, M., Patel, V., Paulusma, D. & Trunck, T. (2010), Obtaining online ecological colourings by generalizing first-fit, 6072: 5th International Computer Science Symposium in Russia (CSR 2010). Springer, 240-251.
- Biro, P., Kern, W. & Paulusma, D. (2010), On solution concepts for matching games, in Kratochvíl, Jan, Li, Angsheng Fiala, Jirí & Kolman, Petr eds, Lecture Notes in Computer Science 6108: 7th Annual Conference on Theory and Applications of Models of Computation. Prague, Czech Republic, Springer, Prague, 211-221.
- Ordyniak, S., Paulusma, D. & Szeider, S. (2010), Satisfiability of Acyclic and Almost Acyclic CNF Formulas, Leibniz International Proceedings in Informatics (LIPIcs) 8: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). 84-95.
- Hof P. van 't Kaminski M., Paulusma, D., Szeider S. & Thilikos D. M. (2010), On contracting graphs to fixed pattern graphs, in van Leeuwen, Jan, Muscholl, Anca, Peleg, David, Pokorný, Jaroslav & Rumpe, Bernhard eds, Lecture Notes in Computer Science 5901: 36th Conference on Current Trends in Theory and Practice of Computer Science. Špindleruv Mlýn, Czech Republic, Springer, pindleruv Mln, 503-514.
- Broersma, H.J., Golovach, P.A., Paulusma, D. & Song, J. (2010), Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs, 6410: 63-74.
- Kaminski, M., Paulusma, D. & Thilikos, D. M. (2010), Contractions of planar graphs in polynomial time, Lecture Notes in Computer Science 6346: The 18th Annual European Symposium. Springer, 122-133.
- Chalopin, J. & Paulusma, D. (2010), Packing bipartite graphs with covers of complete bipartite graphs, in Calamoneri, Tiziana & Diaz, Josep eds, Lecture Notes in Computer Science 6078: 7th International Conference on Algorithms and Complexity. Rome, Italy, Springer, Rome, 276-287
- Hof, P. van 't, Paulusma, D. & Woeginger, G.J. (2009), Partitioning graphs into connected parts, Lecture Notes in Computer Science 5675: Fourth International Computer Science Symposium in Russia (CSR 2009). Novosibirsk, Russia, Springer, Novosibirsk, 143-154.
- Ito, T., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2009), Parameterizing cut sets in a graph by the number of their components, in Dong, Y., Du, D.-Z. & Ibarra, O. eds, Lecture Notes in Computer Science 5878: 20th International Symposium on Algorithms and Computation (ISAAC 2009). Honolulu, Hawaii, United States, Springer, Honolulu HI, 605-615.
- Golovach, P.A., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2009), Induced packing of odd cycles in a planar graph, in Dong, Y., Du, D.-Z. & Ibarra, O. eds, Lecture Notes in Computer Science 5878: 20th International Symposium on Algorithms and Computation (ISAAC 2009). Honolulu, Hawaii, United States, Springer, Honolulu HI, 514-523.
- Hof, P. van 't, Paulusma, D. & Rooij, J.M.M. van (2009), Computing role assignments of chordal graphs, Lecture Notes in Computer Science 5699: 17th International Symposium on Fundamentals of Computation Theory (FCT 2009). Wrocław, Poland, Springer, Berlin Heidelberg, 193-204.
- Broersma, H.J., Fomin, F.V., Hof van 't, P. & Paulusma, D. (2009), Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs, in Habib, M. & Paul, C. eds, Lecture Notes in Computer Science 5911: 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009). Montpellier, France, Springer, Montpellier, 44-53.
- Paulusma, D. & Rooij van, J.M.M. (2009), On partitioning a graph into two connected subgraphs, in Dong, Y., Du, D.-Z. & Ibarra, O. eds, Lecture Notes in Computer Science 5878: 20th International Symposium on Algorithms and Computation. Honolulu, Hawaii, United States, Springer, Honolulu HI, 1215-1224.
- Hof van 't, P., Kaminski, M. & Paulusma, D. (2009), Finding Induced Paths of Given Parity in Claw-Free Graphs, in Paul, C. & Habib, M. eds, Lecture Notes in Computer Science 5911: 35th International Workshop on Graph-Theoretic Concepts in Computer Science. Montpellier, France, Springer, Montpellier, 341-352.
- Broersma, H.J., Fomin, F.V., Golovach, P.A. & Paulusma, D. (2009), Three complexity results on coloring Pk-free graphs, in Fiala, J., Kratochvíl, J. & Miller, M. eds, Lecture Notes in Computer Science 5874: 20th International Workshop on Combinatorial Algorithms (IWOCA 2009). Hradec nad Moravicí, Czech Republic, Springer, Hradec nad Moravic, 95-104.
- Fiala, J. & Paulusma, D. (2008), Comparing universal covers in polynomial time, in Hirsch, Edward A. Razboro, Alexander A. Semenov, Alexei & Slissenko, Anatol eds, Lecture Notes in Computer Science 5010: 3rd International Computer Science Symposium in Russia. Moscow, Russia, Springer, Moscow, 158-167.
- Hof, P. van 't & Paulusma, D. (2008), A new characterization of P6-free graphs, in Hu, Xiaodong & Wang, Jie eds, Lecture Notes in Computer Science 5092: 14th Annual International Computing and Combinatorics Conference. Dalian, China, Springer, Berlin Heidelberg, 415-424.
- Broersma, H. J. & Paulusma, D. (2008), Computing sharp 2-factors in claw-free graphs, in Ochmanski, Edward & Tyszkiewicz, Jerzy eds, Lecture Notes in Computer Science 5162: 33th International Symposium on Mathematical Foundations of Computer Science. Toru´n, Poland Springer, Torun, 193-204.
- Broersma, H.J., Marchal, B., Paulusma, D. & Salman, A.N.M. (2007), Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars, 4362: SOFSEM 2007. 188-199.
- Fleischner, H., Mujuni, E., Paulusma, D. & Szeider, S. (2007), Covering Graphs with Few Complete Bipartite Subgraphs, 4855: 340-351.
- Broersma, H.J., Paulusma, D. & Yoshimoto, K. (2007), On components of 2-factors in claw-free graphs, 29: European Conference on Combinatorics, Graph Theory and Applications. Elsevier, 289-293.
- Broersma, H.J., Johnson, M. & Paulusma, D. (2007), Upper Bounds and Algorithms for Parallel Knock-Out Numbers, 4474: 328-340.
- Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2006), The computational complexity of the parallel knock-out problem, Lecture Notes in Computer Science 3887: 7th Latin American Theoretical Informatics Symposium (LATIN 2006). Valdivia, Chile., Springer, Berlin, 250-261.
- Chalopin, J. & Paulusma, D. (2006), Graph Labelings Derived from Models in Distributed Computing, 4271: 301-312.
- Broersma, H.J., Capponi, A. & Paulusma, D. (2006), On-line coloring of H-free bipartite graphs, in Calamoneri, T. Finocchi, I. & Italiano, G.F. eds, Lecture Notes in Computer Science 3998: 6th Italian Conference on Algorithms and Complexity (CIAC 2006). Rome, Italy, Springer-Verlag, Rome, 284-295.
- Fiala, J. Paulusma, D. & Telle, J. A. (2005), Matrix and graph orders derived from locally constrained graph homomorphisms, in Jedrzejowicz, J. & Szepietowski, A. eds, Lecture Notes in Computer Science 3618: 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Gdansk, Poland, Springer, Gdansk, 12.
- Fiala, J., Paulusma, D. & Telle, J.A. (2005), Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms, 3787: 115-126.
- Smit, L.T., Smit, G.J.M., Hurink, J.L., Broersma, H.J., Paulusma, D. & Wolkotte, P.T. (2004), Run-time assignment of tasks to multiple heterogeneous processors, 5th PROGRESS Symposium on Embedded Systems. Nieuwegein, The Netherlands, Nieuwegein, 185-192.
- Smit, L.T., Smit, G.J.M., Hurink, J.L., Broersma, H.J., Paulusma, D. & Wolkotte, P.T. (2004), Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture, Proceedings. 2004 IEEE International Conference on Field- Programmable Technology (IEEE Cat. No.04EX921). 421-424.
- Broersma, H.J., Paulusma, D., Smit, G.J.M., Vlaardingerbroek, F. & Woeginger, G.J. (2004), The Computational Complexity of the Minimum Weight Processor Assignment Problem, 3353: 189-200.
- Levin, A., Paulusma, D. & Woeginger, G.J. (2003), The complexity of graph contractions, 2880: 322-333.
- Fiala, J. & Paulusma, D. (2003), The Computational Complexity of the Role Assignment Problem, 2719: 817-828.
Journal Article
- Brettell, N., Johnson, M. & Paulusma, D. (2022). Computing Weighted Subset Odd Cycle Transversals in H-free graphs. Journal of Computer and System Sciences 128: 71-85.
- Martin, B., Paulusma, D. & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics 314: 150-161.
- Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S. & Zivny S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic
- Brettell, N., Johnson, M., Paesani, G. & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science 902: 76-92.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2022). Induced disjoint paths in AT-free graphs. Journal of Computer and System Sciences 124: 170-191.
- Kern, W., Martin, B., Paulusma, D., Smith, S. & van Leeuwen, E.J. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science 898: 59-68.
- Martin, B., Paulusma, D. & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters 174: 106213.
- Johnson, M. Paulusma, D. & van Leeuwen, E.J. (2021). What graphs are 2-dot product graphs? International Journal of Computational Geometry and Applications 31(01): 1-16.
- Brettell, N., Horsfield, J., Munaro, A., Paesani, G. & Paulusma, D. (2022). Bounding the mim-width of hereditary graph classes. Journal of Graph Theory 99(1): 117-151.
- Brettell, N., Horsfield, J., Munaro, A. & Paulusma, D. (2022). List k-colouring P-free graphs: a mim-width perspective. Information Processing Letters 173: 106168.
- Bonamy, Marthe, Dabrowski, Konrad K., Feghali, Carl, Johnson, Matthew & Paulusma, Daniël (2021). Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration. Journal of Graph Theory 98(1): 81-109.
- Bodlaender, H.L., Brettell, N., Johnson, M., Paesani, G., Paulusma, D. & van Leeuwen, E.J. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science 867: 30-39.
- Dabrowski, K.K. Dross, F., Jeong, J., Kante, M.M., Kwon, O., Oum, S. & Paulusma, D. (2021). Tree pivot-minors and linear rank-width. SIAM Journal on Discrete Mathematics
- Bonamy, M., Bousquet, N., Dabrowski, K.K., Johnson, M., Paulusma, D. & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica 83(3): 822-852.
- Martin, B., Paulusma, D. & van Leeuwen, E.J. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences 113: 60-75.
- Blanché, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D. & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics 34(2): 1107-1147.
- Dabrowski, K.K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D. & Rzążewski, P. (2020). On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica 82(10): 2841-2866.
- Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D.l & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica 82(7): 1833-1858.
- Hof, F. Kern, W. Kurz, S., Pashkovich, K. & Paulusma, D. (2020). Simple games versus weighted voting games: bounding the critical threshold value. Social Choice and Welfare 54(4): 609-621.
- Dabrowski, K.K., Lozin, V.V. & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences 108: 64-91.
- Gaspers, S., Huang, S. & Paulusma, D. (2019). Colouring Square-Free Graphs without Long Induced Paths. Journal of Computer and System Sciences 106: 60-79.
- Johnson, M., Paesani, G. & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica 82(1): 20-40.
- Bonsma, P. & Paulusma, D. (2019). Using contracted solution graphs for solving reconfiguration problems. Acta Informatica 56(7-8): 619-648.
- Dabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory 92(4): 377-393.
- Golovach, P.A.,, Heggernes, P., Kratch, D., Lima, P.T. & Paulusma D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica 81(7): 2795-2828.
- Galby, E. Lima, P.T. Paulusma, D. & Ries, B. (2019). Classifying k-Edge Colouring for H-free Graphs. Information Processing Letters 146: 39-43.
- Larose, B., Martin, B. & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory 11(1): 3.
- Blanché, A., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory 91(3): 267-289.
- Paulusma, D. & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters 143: 34-36.
- Paulusma, D., Picouleau, C. & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics 257: 361-367.
- Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2019). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica 81(4): 1342-1369.
- Diner, Ö.Y., Paulusma, D., Picouleau, C. & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science 746: 49-72.
- Golovach, P.A., Johnson, M., Martin, B., Paulusma, D. & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability 8(1): 27-42.
- Dabrowski, K.K. & Paulusma, D. (2018). On colouring (2P2,H)-free and (P5,H)-free graphs. Information Processing Letters 134: 35-41.
- Golovach, P.A., Kratsch, D., Stewart, A. & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems 62(6): 1409-1426.
- Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters 131: 26-32.
- Chiarelli, N., Hartinger, T. R., Johnson, M., Milanič, M. & Paulusma, D. (2018). Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoretical Computer Science 705: 75-83.
- Dabrowski, K.K. & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters 127: 37-42.
- Dabrowski, K.K., Lozin, V.V. & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order 35(2): 253-274.
- Dabrowski, K.K., Dross, F. & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences 89: 410-431.
- Golovach, P.A., Kratsch, D., Paulusma, D. & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science 689: 36-47.
- Cochefert, M., Couturier, J-F., Golovach, P.A., Kratsch, D., Paulusma, D. & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics 248: 93-101.
- Biró, P., Kern, W., Paulusma, D. & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior 108: 245-268.
- Brandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory 86(1): 42-77.
- Dabrowski, K.K., Golovach, P.A., van 't Hof, P., Paulusma, D. & Thilikos, D.M. (2017). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences 85: 168-182.
- Belmonte, R., van ’t Hof, P., Kamiński, M. & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics 217(Part 2): 132-143.
- Kamiński, M., Paulusma, D., Stewart, A. & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks 68(4): 250-259.
- Feghali, C., Johnson, M. & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics 59: 1-10.
- Dabrowski, K.K., Huang, S. & Paulusma, D. (2019). Bounding clique-width via perfect graphs. Journal of Computer and System Sciences 104: 202-215.
- Hartinger, T.R., Johnson, M., Milanič, M. & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics 58: 203-224.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science 640: 70-83.
- Brandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics 211: 30-39.
- Golovach, P.A., Johnson, M., Paulusma, D. & Song. J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory 84(4): 331-363.
- Dabrowski, K.K., Golovach, P.A., van 't Hof, P. & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences 82(2): 213-228.
- Feghali, C., Johnson, M. & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory 83(4): 340-358.
- Paulusma, D., Slivovsky, S. & Szeider, S. (2016). Model counting for CNF formulas of bounded modular treewidth. Algorithmica 76(1): 168-194.
- Dabrowski, K.K. & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics 200: 43-51.
- Johnson, M., Kratsch, D., Kratsch, S., Patel, V. & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica 75(2): 295-321.
- Johnson, M., Paulusma, D. & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics 190-191: 100-108.
- Golovach, P.A., Paulusma, D. & Ries, B. (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics 180: 101-110.
- Chaplick, S., Fiala, J., Hof, van 't P., Paulusma, D. & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical computer science 590: 86-95.
- Dabrowski, K.K. & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal
- Johnson, M., Paulusma, D. & van Leeuwen, E.J. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks 41: 48-55.
- Huang, S., Johnson, M. & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal 58(11): 3074-3088.
- Golovach, P.A., Paulusma, D. & van Leeuwen, E.J. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics 29(1): 348-375.
- Broersma, H.J., Fiala, J., Golovach, P.A., Kaiser, T., Paulusma, D. & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory 79(4): 282-299.
- Martin, B. & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B 111: 17-37.
- Golovach, P.A., Paulusma, D. & Stewart, I.A. (2017). Graph editing to a fixed target. Discrete Applied Mathematics 216(Part 1): 181-190.
- Golovach, P.A., Paulusma, D. & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation 237: 204-214.
- Biró, P., Bomhoff, M., Golovach, P.A., Kern, W. & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science 540-541: 53-61.
- Bonamy, M, Johnson, M, Lignos, I, Patel, V & Paulusma, D (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27(1): 132-143
- Johnson, M., Patel, V., Paulusma, D. & Trunck, T. (2014). Obtaining Online Ecological Colourings by Generalizing First-Fit. Theory of Computing Systems 54(2): 244-260.
- Dabrowski, K.K., Golovach, P.A. & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science 522: 34-43.
- Chalopin, J. & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics 168: 40-50.
- Belmonte, R., Golovach, P.A., Hof, van 't P. & Paulusma, D. (2014). Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica 51(7): 473-497.
- Golovach, P.A. & Paulusma, D. (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics 166: 123-130.
- Golovach, P.A., Paulusma, D., Kaminski, M. & Thilikos, D.M. (2014). Lift-contractions. European Journal of Combinatorics 35: 286-296.
- Golovach, P.A., Paulusma, D. & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics 167: 107-120.
- Cochefert, M., Couturier, J-F., Golovach, P.A. & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica
- Belmonte, R., Golovach, P.A., Heggernes, P., van 't Hof, P., Kaminski, M. & Paulusma, D. (2014). Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica 69(3): 501-521.
- Golovach, P.A., Heggernes, P., Hof, van 't P., Manne, F., Paulusma, D. & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica 72(1): 99-125.
- Couturier, J., Golovach, P.A., Kratsch, D. & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica 71(1): 21-35.
- Golovach, P.A., Heggernes, P., van 't Hof, P. & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters 113(4): 107-110.
- Golovach, P.A., Kratsch, D. & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science 482: 20-32.
- Golovach P.A., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science 481: 74-84.
- Golovach, P.A., van 't Hof, P. & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science 476: 38-46.
- Ordyniak, S., Paulusma, D. & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science 481: 85-99.
- Belmonte, R., Hof, van 't P., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics 161(13-14): 1888-1893.
- Golovach, P.A., Paulusma, D. & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics 161(1-2): 140-150.
- Broersma, H.J., Fomin, F.V., Hof van 't, P. & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica 65(1): 129-145.
- Fiala, J., Kaminski, M. & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics and Theoretical Computer Science 15(2): 223-232.
- Broersma, H.J., Fomin, F.V., Golovach, P.A. & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics 34(3): 609-619.
- Heggernes, P., van 't Hof, P. & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of Discrete Algorithms 14: 173-188.
- Fiala, J., Kamiński, M., Lidický, B. & Paulusma, D. (2012). The k-in-a-path problem for claw-free graphs. Algorithmica 62(1-2): 499-519.
- Fiala, J., Kaminksi, M. & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of Discrete Algorithms 17: 74–85.
- Golovach, P.A., Paulusma, D. & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science 457: 86-100.
- Hof van 't, P., Kamiński, M. & Paulusma, D. (2012). Finding induced paths of given parity in claw-free graphs. Algorithmica 62(1-2): 537-563.
- Golovach, P.A. Kamiński, M., Paulusma, D. & Thilikos, D.M. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science 420: 28-35.
- Couturier, J.F., Golovach, P.A., Kratsch, D. & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of Discrete Algorithms 15: 56–62.
- Biro, P., Kern, W. & Paulusma, D. (2012). Computing solutions for matching games. International Journal of Game Theory 41(1): 75-90.
- Golovach, P.A., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2012). Containment relations in split graphs. Discrete Applied Mathematics 160(1-2): 155-163.
- Broersma, H.J., Golovach, P.A., Paulusma, D. & Song, J. (2012). Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science 414(1): 9-19.
- Fiala, J., Golovach, P.A., Kratochvil, J., Lidický, B. & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics 160(6): 764-779.
- Broersma, H.J., Golovach, P.A., Paulusma, D. & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science 423: 1-10.
- Golovach, P.A., Lidicky, B., Martin, B. & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica 49(6): 381-394.
- Hof, P. van 't, Kaminski, M., Paulusma, D., Szeider, S. & Thilikos, D.M. (2012). On graph contractions and induced minors. Discrete Applied Mathematics 160(6): 799–809.
- Ito, T., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2011). Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science 412(45): 6340-6350.
- Chalopin, J. & Paulusma, D. (2011). Graph labelings derived from models in distributed computing: a complete complexity classification. Networks 58(3): 207-231.
- Paulusma, D & Rooij van, J.M.M. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science 412(48): 6761-6769.
- Ito, T., Kaminski, M., Paulusma, D. & Thilikos, D.M. (2011). On disconnected cuts and separators. Discrete Applied Mathematics 159(13): 1345-1351.
- Kamiński, M., Paulusma, D. & Thilikos, D.M. (2011). Contracting planar graphs to contractions of triangulations. Journal of Discrete Algorithms 9(3): 299-306.
- Hof, P van 't, Paulusma, D. & Rooij, J.M.M. van (2010). Computing role assignments of chordal graphs. Theoretical Computer Science 411(40-42): 3601-3613.
- Hof, P. van 't & Paulusma D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics 158(7): 731-740.
- Johnson, M., Paulusma, D. & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics 310(9): 1413-1423.
- Broersma, H.J. & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of Discrete Algorithms 8(3): 321-329.
- Fiala, J. & Paulusma. D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems 46(4): 620-635.
- Kern, W. & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research 34(4): 981-991.
- Broersma, H.J., Johnson, M. & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science 410(14): 1319-1327.
- Broersma, H. J., Marchal, L., Paulusma, D. & Salman, A. N. M. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae Graph Theory 29(1): 143-162.
- Fleischner, H., Mujuni, E., Paulusma, D. & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science 410(21-23): 2045-2053.
- Broersma, H. J. Fujisawa, J., Marchal, L., Paulusma, D., Salman, A. N. M. & Yoshimoto, K. (2009). Lambda-Backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics 309(18): 5596-5609.
- Broersma, H.J., Paulusma, D. & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics 25(4): 427-460.
- Hof, P. van 't Paulusma, D. & Woeginger, G.J. (2009). Partitioning graphs into connected parts. Theoretical Computer Science 410(47-49): 4834-4843.
- Levin, A., Paulusma, D. & Woeginger, G.J. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks 51(3): 178-189.
- Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science 393(1-3): 182-195.
- Broersma, H.J., Capponi, A. & Paulusma, D (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics 22(1): 72-91.
- Paulusma, D. & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics 308(7): 1222-1229.
- Fiala, J., Paulusma, D. & Telle, J.A. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics 29(4): 850-880.
- Levin, A., Paulusma, D. & Woeginger, G. J. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks 52(1): 32-56.
- Paulusma, D. & Yoshimito, K. (2007). Cycles through specified vertices in triangle-free graphs. Discussiones Mathematicae Graph Theory 27(1): 179-191.
- Fiala, J. & Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical computer science 349(1): 67-81.
- Kern, W. & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete optimization 1(2): 205-214.
- Kern, W. & Paulusma, D. (2003). Matching games the least core and the nucleolus. Mathematics of operations research 28(2): 294-308.
- Driessen, T.S.H. & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research 53(1): 35-49.
- Kern, W. & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics 108(3): 317-323.
- Faigle, U., Kern, W. & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical Methods of Operations Research 52(1): 23-38.
Report
Supervision students
Miss Xin Ye
Postgraduate Student