Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Professor Daniel Paulusma - all publications

Journal Article

Conference Paper

  • 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.
  • 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).
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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., 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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), 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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. & 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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, Lübeck, 201-212.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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-Universität zu Kiel, 55--66.
  • 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.
  • 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, Lübeck, 177-188.
  • 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.
  • 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.
  • 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. & 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., 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, 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., 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., 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
  • 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., 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.
  • 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
  • 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.
  • 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., 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.
  • 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.
  • 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., Kamiński, M., Paulusma, D. & Thilikos, D.M. (2011), Lift Contractions, 38: Elsevier, 407-412.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Broersma, H.J., Golovach, P.A., Paulusma, D. & Song, J. (2010), On Coloring Graphs without Induced Forests, 6507: 156-167.
  • 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 Mlýn, 503-514.
  • 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.
  • 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
  • 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.
  • 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.
  • 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
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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, Toru´n, 193-204.
  • Fleischner, H., Mujuni, E., Paulusma, D. & Szeider, S. (2007), Covering Graphs with Few Complete Bipartite Subgraphs, 4855: 340-351.
  • Broersma, H.J., Marchal, B., Paulusma, D. & Salman, A.N.M. (2007), Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars, 4362: 188-199.
  • 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.
  • 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.
  • 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.
  • Fiala, J., Paulusma, D. & Telle, J.A. (2005), Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms, 3787: 115-126.
  • 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.
  • 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.

Report