Staff profile
Overview
https://apps.dur.ac.uk/biography/image/39
Professor Daniel Paulusma
Professor
Affiliation | Telephone |
---|---|
Professor in the Department of Computer Science | +44 (0) 191 33 41723 |
Publications
Chapter in book
- Maximizing Matching Cuts
Le, V. B., Lucke, F., Paulusma, D., & Ries, B. (2024). Maximizing Matching Cuts. In P. M. Pardalos, & O. A. Prokopyev (Eds.), Encyclopedia of Optimization (1-10). Springer Nature. https://doi.org/10.1007/978-3-030-54621-2_898-1
Conference Paper
- The Complexity of Diameter on H-free Graphs
Oostveen, J. J., Paulusma, D., & van Leeuwen, E. J. (2024, June). The Complexity of Diameter on H-free Graphs. Presented at WG 2024, Gozd Martuljek, Slovenia - Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,
Lucke, F., Momeni, A., Paulusma, D., & Smith, S. (2024, June). Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,. Presented at WG 2024, Gozd Martuljek, Slovenia - Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs
Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024 - Complexity framework for forbidden subgraphs IV: The Steiner Forest problem
Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, July). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Presented at IWOCA, Ischia, Italy - Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland - Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded
Benedek, M., Biró, P., Csáji, G., Johnson, M., Paulusma, D., & Ye, X. (2024, May). Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded. Presented at AAMAS, Auckland, New Zealand - Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
Lucke, F., Paulusma, D., & Ries, B. (2023, August). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France - Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France - Matching cuts in graphs of high girth and H-free graphs
Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (2023, December). Matching cuts in graphs of high girth and H-free graphs. Presented at ISAAC 2023 - Computing Subset Vertex Covers in H-Free Graphs
Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., & van Leeuwen, E. J. (2023, September). Computing Subset Vertex Covers in H-Free Graphs. Presented at FCT 2023: Fundamentals of Computation Theory, Trier, Germany - Computing Balanced Solutions for Large International Kidney Exchange Schemes
Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022, May). Computing Balanced Solutions for Large International Kidney Exchange Schemes. Presented at AAMAS ' 22: International Conference on Autonomous Agents and Multi-Agent Systems, Virtual Event / New Zealand - Finding matching cuts in H-free graphs
Lucke, F., Paulusma, D., & Ries, B. (2021, December). Finding matching cuts in H-free graphs. Presented at 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, South Korea - Classifying Subset Feedback Vertex Set for H-free graphs
Paesani, G., Paulusma, D., & Rzążewski, P. (2022, December). Classifying Subset Feedback Vertex Set for H-free graphs. Presented at WG 2022 - Few induced disjoint paths for H-free graphs
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022, May). Few induced disjoint paths for H-free graphs. Presented at ISCO 2022, Online - Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs - The Complexity of L(p,q)-Edge-Labelling
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022, March). The Complexity of L(p,q)-Edge-Labelling. Presented at The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), University of Jember, East Java - An algorithmic framework for locally constrained homomorphisms
Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022, December). An algorithmic framework for locally constrained homomorphisms. Presented at WG 2022 - Injective colouring for H-free graphs
Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2023, June). Injective colouring for H-free graphs. Presented at CSR 2021, Sochi - Steiner trees for hereditary graph classes
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo - Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
Paesani, G., Paulusma, D., & Rzążewski, P. (2021, August). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. Presented at MFCS 2021, Tallinn, Estonia - Acyclic, star and injective colouring: bounding the diameter
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. Acyclic, star and injective colouring: bounding the diameter - Partitioning H-free graphs of bounded diameter
Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021, December). Partitioning H-free graphs of bounded diameter. Presented at 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan - Colouring graphs of bounded diameter in the absence of small cycles
Martin, B., Paulusma, D., & Smith, S. (2021, May). Colouring graphs of bounded diameter in the absence of small cycles. Presented at CIAC 2021, Virtual Event - Computing weighted subset transversals in H-free graphs
Brettell, N., Johnson, M., & Paulusma, D. (2021, August). Computing weighted subset transversals in H-free graphs. Presented at WADS 2021, Halifax, Nova Scotia - QCSP on reflexive tournaments
Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021, September). QCSP on reflexive tournaments. Presented at The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online - Disjoint paths and connected subgraphs for H-free graphs
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Disjoint paths and connected subgraphs for H-free graphs - Solving problems on generalized convex graphs via mim-width
Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. Solving problems on generalized convex graphs via mim-width - Computing subset transversals in H-free graphs
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020, December). Computing subset transversals in H-free graphs. Presented at WG 2020, Leeds, England - Clique-Width: Harnessing the Power of Atoms
Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020, June). Clique-Width: Harnessing the Power of Atoms. Presented at WG 2020, Leeds, England - Bounding the mim-width of hereditary graph classes
Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020, December). Bounding the mim-width of hereditary graph classes. Presented at IPEC 2020 - Contracting to a longest path in H-free graphs
Kern, W., & Paulusma, D. (2020, December). Contracting to a longest path in H-free graphs. Presented at ISAAC 2020, Hong Kong, China - Acyclic, star and injective colouring: a complexity picture for H-free graphs
Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020, September). Acyclic, star and injective colouring: a complexity picture for H-free graphs. Presented at ESA 2020, Pisa, Italy (Virtual Event) - Colouring H-free graphs of bounded diameter
Martin, B., Paulusma, D., & Smith, S. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany - Tree pivot-minors and linear rank-width
Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019, July). Tree pivot-minors and linear rank-width. Presented at EuroComb 2019, Bratislava, Slovakia - Independent transversals versus transversals
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia - On cycle transversals and their connected variants in the absence of a small linear forest
Feghali, C., Johnson, M., Paesani, G., & Paulusma, D. (2019, August). On cycle transversals and their connected variants in the absence of a small linear forest. Presented at FCT 2019, Copenhagen, Denmark - Generalized matching games for international kidney exchange
Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (2019, December). Generalized matching games for international kidney exchange. Presented at AAMAS 2019, Montreal, Canada - Finding a small number of colourful components
Bulteau, L., Dabrowski, K., Fertin, G., Johnson, M., Paulusma, D., & Vialette, S. (2019, December). Finding a small number of colourful components. Presented at CPM 2019, Pisa, Italy - Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019, December). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Presented at WADS 2019, Edmonton, Canada - Colouring (Pr+Ps)-free graphs
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2018, December). Colouring (Pr+Ps)-free graphs. Presented at 29th International Symposium on Algorithms and Computation (ISAAC 2018)., Jiaoxi, Yilan County, Taiwan - Connected Vertex Cover for (sP1+P5)-free graphs
Johnson, M., Paesani, G., & Paulusma, D. (2018, June). Connected Vertex Cover for (sP1+P5)-free graphs. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany - Computing small pivot-minors
Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany - Simple games versus weighted voting games
Hof, F., Kern, W., Kurz, S., & Paulusma, D. (2018, September). Simple games versus weighted voting games. Presented at 11th International Symposium on Algorithmic Game Theory (SAGT 2018)., Beijing, China - Colouring Square-Free Graphs without Long Induced Paths
Gaspers, S., Huang, S., & Paulusma, D. (2023, February). Colouring Square-Free Graphs without Long Induced Paths. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France - Surjective H-Colouring over Reflexive Digraphs
Larose, B., Martin, B., & Paulusma, D. (2023, February). Surjective H-Colouring over Reflexive Digraphs. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France - On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK - Disconnected Cuts in Claw-free Graphs
Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018, August). Disconnected Cuts in Claw-free Graphs. Presented at 26th Annual European Symposium on Algorithms (ESA 2018)., Helsinki, Finland - Clique-Width for Graph Classes Closed under Complementation
Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017, August). Clique-Width for Graph Classes Closed under Complementation. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark - Recognizing Graphs Close to Bipartite Graphs
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, August). Recognizing Graphs Close to Bipartite Graphs. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark - Clique-width and well-quasi ordering of triangle-free graph classes
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017, June). Clique-width and well-quasi ordering of triangle-free graph classes. Presented at WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Eindhoven, The Netherlands - Reducing the chromatic number by vertex or edge deletions
Picouleau, C., Paulusma, D., & Ries, B. Reducing the chromatic number by vertex or edge deletions. Presented at LAGOS 2017: The IX Latin and American Algorithms, Graphs and Optimization Symposium., Marseille, France - Contracting bipartite graphs to paths and cycles
Dabrowski, K., & Paulusma, D. Contracting bipartite graphs to paths and cycles. Presented at Eurocomb 2017: European Conference on Combinatorics, Graph Theory and Applications., Vienna, Austria - Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Golovach, P., Heggernes, P., Kratsch, D., Lima, P., & Paulusma, D. (2017, June). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Presented at 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Eindhoven, The Netherlands - Surjective H-Colouring: new hardness results
Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017, June). Surjective H-Colouring: new hardness results. Presented at Computability in Europe (CiE 2017)., Turku, Finland - Blocking independent sets for H-free graphs via edge contractions and vertex deletions
Paulusma, D., Picouleau, C., & Ries, B. (2017, April). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. Presented at Theory and applications of models of computation, 14th Annual Conference, TAMC 2017, Bern, Switzerland - Independent Feedback Vertex Set for P5-free Graphs
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, December). Independent Feedback Vertex Set for P5-free Graphs. Presented at ISAAC 2017 - Squares of low clique number
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. Squares of low clique number. Presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16), Gargnano, Italy - Reducing the clique and chromatic number via edge contractions and vertex deletions
Paulusma, D., Picouleau, C., & Ries, B. (2016, May). Reducing the clique and chromatic number via edge contractions and vertex deletions. Presented at 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy - Well-quasi-ordering versus clique-width: new results on bigenic classes
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland - Finding cactus roots in polynomial time
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016, August). Finding cactus roots in polynomial time. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland - The stable fixtures problem with payments
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2015, June). The stable fixtures problem with payments. Presented at 41 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany - Open problems on graph coloring for special graph classes
Paulusma, D. (2015, June). Open problems on graph coloring for special graph classes. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany - Using contracted solution graphs for solving reconfiguration problems
Bonsma, P., & Paulusma, D. (2016, August). Using contracted solution graphs for solving reconfiguration problems. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Krakow, Poland - Colouring diamond-free graphs
Dabrowski, K. K., Dross, F., & Paulusma, D. (2016, June). Colouring diamond-free graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland - A linear kernel for finding square roots of almost planar graphs
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016, June). A linear kernel for finding square roots of almost planar graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland - Filling the complexity gaps for colouring planar and bounded degree graphs
Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2015, October). Filling the complexity gaps for colouring planar and bounded degree graphs. Presented at 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Verona, Italy - What graphs are 2-dot product graphs?
Johnson, M., van Leeuwen, E., & Paulusma, D. (2015, November). What graphs are 2-dot product graphs?. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway - Kempe equivalence of colourings of cubic graphs
Feghali, C., Johnson, M., & Paulusma, D. (2015, November). Kempe equivalence of colourings of cubic graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway - Bounding the clique-width of H-free split graphs
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, November). Bounding the clique-width of H-free split graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway - The price of connectivity for cycle transversals
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015, August). The price of connectivity for cycle transversals. Presented at 40th International Symposium, MFCS 2015, Milan, Italy - Bounding the Clique-Width of H-free Chordal Graphs
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, August). Bounding the Clique-Width of H-free Chordal Graphs. Presented at 40th International Symposium, MFCS 2015, Milan, Italy - Minimal disconnected cuts in planar graphs
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015, August). Minimal disconnected cuts in planar graphs. Presented at 20th International Symposium, FCT 2015, Gdańsk, Poland - Editing to a planar graph of given degrees
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2015, June). Editing to a planar graph of given degrees - Clique-width of graph classes defined by two forbidden induced subgraphs
Dabrowski, K. K., & Paulusma, D. (2015, March). Clique-width of graph classes defined by two forbidden induced subgraphs. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France - Contraction blockers for graphs with forbidden induced paths
Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2015, March). Contraction blockers for graphs with forbidden induced paths. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France - Bounding clique-width via perfect graphs
Dabrowski, K. K., Huang, S., & Paulusma, D. (2015, March). Bounding clique-width via perfect graphs. Presented at International Conference on Language and Automata Theory and Applications, Nice, France - Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2014, December). Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary - Classifying the Clique-Width of H-Free Bipartite Graphs
Dabrowski, K. K., & Paulusma, D. (2014, December). Classifying the Clique-Width of H-Free Bipartite Graphs. Presented at 20th International Conference, COCOON 2014, Atlanta, GA, USA - Knocking Out P_k-free Graphs
Johnson, M., Paulusma, D., & Stewart, A. (2014, December). Knocking Out P_k-free Graphs. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary - Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs
Huang, S., Johnson, M., & Paulusma, D. (2014, December). Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs. Presented at 10th International Conference, AAIM 2014, Vancouver, BC, Canada - Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
Golovach, P., Paulusma, D., & van Leeuwen, E. (2014, December). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. Presented at 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France - A Reconfigurations Analogue of Brooks’ Theorem
Feghali, C., Johnson, M., & Paulusma, D. (2014, December). A Reconfigurations Analogue of Brooks’ Theorem. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary - Finding Shortest Paths Between Graph Colourings
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2014, December). Finding Shortest Paths Between Graph Colourings. Presented at 9th International Symposium, IPEC 2014, Wroclaw, Poland - Editing to Eulerian Graphs
Dabrowski, K. K., Golovach, P. A., Hof, V. P., & Paulusma, D. (2014, December). Editing to Eulerian Graphs. Presented at 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), Budapest, Hungary - Sparse Square Roots
Cochefert, M., Couturier, J.-F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013, December). Sparse Square Roots. Presented at 39th International Workshop, WG 2013, Lübeck, Germany - Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013, December). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Presented at 39th International Workshop, WG 2013, Lübeck, Germany - Model counting for CNF formuals of bounded module treewidth
Paulusma, D., Slivovksy, F., & Szeider, S. (2013, December). Model counting for CNF formuals of bounded module treewidth. Presented at 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Christian-Albrechts-Universität zu Kiel, Germany - Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
Johnson, M., Paulusma, D., & van Leeuwen, E. (2013, December). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. Presented at 24th International Symposium, ISAAC 2013, Hong Kong, China, - The price of connectivity for feedback vertex set
Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013, December). The price of connectivity for feedback vertex set. Presented at 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013, Pisa, Italy - Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2013, December). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Presented at 8th International Symposium, IPEC 2013, Sophia Antipolis, France - Graph editing to a fixed target
Golovach, P., Paulusma, D., & Stewart, I. A. (2013, December). Graph editing to a fixed target. Presented at International Workshop on Combinatorial Algorithms, Rouen, France - Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesar, M. (2013, December). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. Presented at Liverpool, UK, 19th International Symposium, FCT 2013 - List Coloring in the Absence of Two Subgraphs
Golovach, P. A., & Paulusma, D. (2013, December). List Coloring in the Absence of Two Subgraphs. Presented at 8th International Conference, CIAC 2013, Barcelona, Spain - Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013, December). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Presented at 39th International Workshop, WG 2013, 19-21 June 2013 - Solutions for the stable rommates problem with payments
Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012, December). Solutions for the stable rommates problem with payments - How to eliminate a graph
Golovach, P., Heggernes, P., van 't Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012, December). How to eliminate a graph - Obtaining planarity by contracting few edges
Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012, December). Obtaining planarity by contracting few edges - Characterizing graphs of small carving-width
Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012, December). Characterizing graphs of small carving-width - Coloring graphs characterized by a forbidden subgraph
Golovach, P. A., Paulusma, D., & Ries, B. (2012, December). Coloring graphs characterized by a forbidden subgraph - Detecting induced minors in AT-free graphs
Golovach, P. A., Kratsch, D., & Paulusma, D. (2012, December). Detecting induced minors in AT-free graphs - Closing complexity gaps for coloring problems on H-free graphs
Golovach, P. A., Paulusma, D., & Song, J. (2012, December). Closing complexity gaps for coloring problems on H-free graphs - Finding vertex-surjective graph homomorphisms
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012, December). Finding vertex-surjective graph homomorphisms - 4-Coloring H-free graphs when H is small
Golovach, P., Paulusma, D., & Song, J. (2012, December). 4-Coloring H-free graphs when H is small - Induced disjoint paths in claw-free graphs
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in claw-free graphs - Induced disjoint paths in AT-free graphs
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in AT-free graphs - Lift Contractions
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. Lift Contractions - On the diameter of reconfiguration graphs for vertex colourings
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. On the diameter of reconfiguration graphs for vertex colourings - Computing vertex-surjective homomorphisms to partially reflexive trees
Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Computing vertex-surjective homomorphisms to partially reflexive trees. Presented at 6th International Computer Science Symposium in Russia, CSR 2011., St Petersburg, Russia - List coloring in the absence of a linear forest
Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011, December). List coloring in the absence of a linear forest. Presented at 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic - Coloring graphs without short cycles and long induced paths
Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Coloring graphs without short cycles and long induced paths. Presented at Fundamentals of Computation Theory, 18th International Symposium, FCT 2011, Oslo, Norway - Increasing the Minimum Degree of a Graph by Contractions
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2011, September). Increasing the Minimum Degree of a Graph by Contractions. Presented at IPEC 2011: Parameterized and Exact Computation, Saarbrücken, Germany - Contracting a chordal graph to a split graph or a tree
Golovach, P. A., Kaminski, M., & Paulusma, D. (2011, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, Poland - Satisfiability of acyclic and almost acyclic CNF formulas (II)
Ordyniak, S., Paulusma, D., & Szeider, S. (2011, December). Satisfiability of acyclic and almost acyclic CNF formulas (II). Presented at 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Ann Arbor, MI - Computing Role Assignments of Proper Interval Graphs in Polynomial Time
Heggernes, P., Hof, V. P., & Paulusma, D. (2011, December). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Presented at 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London - The computational complexity of Disconnected Cut and 2K2-Partition
Martin, B., & Paulusma, D. (2011, December). The computational complexity of Disconnected Cut and 2K2-Partition. Presented at Principles and Practice of Constraint Programming, 17th International Conference, CP 2011, Perugia, Italy - Finding contractions and induced minors in chordal graphs via disjoint paths
Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011, December). Finding contractions and induced minors in chordal graphs via disjoint paths. Presented at 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan - Satisfiability of Acyclic and Almost Acyclic CNF Formulas
Ordyniak, S., Paulusma, D., & Szeider, S. (2010, December). Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Presented at IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Chennai, India - Obtaining online ecological colourings by generalizing first-fit
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010, December). Obtaining online ecological colourings by generalizing first-fit. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia - Packing bipartite graphs with covers of complete bipartite graphs
Chalopin, J., & Paulusma, D. (2010, December). Packing bipartite graphs with covers of complete bipartite graphs. Presented at 7th International Conference on Algorithms and Complexity, Rome, Italy - L(2,1,1)-labeling is NP-complete for trees
Golovach, P. A., Lidicky, B., & Paulusma, D. (2010, December). L(2,1,1)-labeling is NP-complete for trees. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic - Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, June). Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs. Presented at WG 2010: Graph-Theoretic Concepts in Computer Science, Zarós, Crete, Greece - On contracting graphs to fixed pattern graphs
't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010, December). On contracting graphs to fixed pattern graphs. Presented at 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic - On Coloring Graphs without Induced Forests
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, December). On Coloring Graphs without Induced Forests. Presented at ISAAC 2010: Algorithms and Computation, Jeju Island, Korea - On solution concepts for matching games
Biro, P., Kern, W., & Paulusma, D. (2010, December). On solution concepts for matching games. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic - Contractions of planar graphs in polynomial time
Kaminski, M., Paulusma, D., & Thilikos, D. (2010, December). Contractions of planar graphs in polynomial time. Presented at The 18th Annual European Symposium - The k-in-a-path problem for claw-free graphs
Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010, December). The k-in-a-path problem for claw-free graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France - Path factors and parallel knock-out schemes of almost claw-free graphs
Johnson, M., Paulusma, D., & Wood, C. (2010, December). Path factors and parallel knock-out schemes of almost claw-free graphs. Presented at 19th International Workshop on Combinatorial Algorithms, Nagoya - Parameterizing cut sets in a graph by the number of their components
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Parameterizing cut sets in a graph by the number of their components. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States - Induced packing of odd cycles in a planar graph
Golovach, P. A., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Induced packing of odd cycles in a planar graph. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States - On partitioning a graph into two connected subgraphs
Paulusma, D., & Rooij van, J. M. M. (2009, December). On partitioning a graph into two connected subgraphs. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States - Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs
Broersma, H. J., Fomin, F. V., Hof van 't, P., & Paulusma, D. (2009, June). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France - Finding Induced Paths of Given Parity in Claw-Free Graphs
Hof van 't, P., Kaminski, M., & Paulusma, D. (2009, December). Finding Induced Paths of Given Parity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science, Montpellier, France - Three complexity results on coloring Pk-free graphs
Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2023, June). Three complexity results on coloring Pk-free graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic - Computing role assignments of chordal graphs
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009, September). Computing role assignments of chordal graphs. Presented at 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw, Poland - Partitioning graphs into connected parts
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009, August). Partitioning graphs into connected parts. Presented at Fourth International Computer Science Symposium in Russia (CSR 2009)., Novosibirsk, Russia - A new characterization of P6-free graphs
Hof, P. V., & Paulusma, D. (2008, December). A new characterization of P6-free graphs. Presented at 14th Annual International Computing and Combinatorics Conference, Dalian, China - Comparing universal covers in polynomial time
Fiala, J., & Paulusma, D. (2008, December). Comparing universal covers in polynomial time. Presented at 3rd International Computer Science Symposium in Russia, Moscow, Russia - Computing sharp 2-factors in claw-free graphs
Broersma, H. J., & Paulusma, D. (2008, December). Computing sharp 2-factors in claw-free graphs. Presented at 33th International Symposium on Mathematical Foundations of Computer Science, Toru´n, Poland - On components of 2-factors in claw-free graphs
Broersma, H., Paulusma, D., & Yoshimoto, K. On components of 2-factors in claw-free graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications - Covering Graphs with Few Complete Bipartite Subgraphs
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2007, December). Covering Graphs with Few Complete Bipartite Subgraphs. Presented at FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, New Delhi, India - Upper Bounds and Algorithms for Parallel Knock-Out Numbers
Broersma, H., Johnson, M., & Paulusma, D. (2007, June). Upper Bounds and Algorithms for Parallel Knock-Out Numbers. Presented at SIROCCO 2007: Structural Information and Communication Complexity, Castiglioncello, Italy - Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars
Broersma, H., Marchal, B., Paulusma, D., & Salman, A. (2007, January). Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars. Presented at SOFSEM 2007, Harrachov, Czech Republic - The computational complexity of the parallel knock-out problem
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile - Graph Labelings Derived from Models in Distributed Computing
Chalopin, J., & Paulusma, D. (2006, June). Graph Labelings Derived from Models in Distributed Computing. Presented at WG 2006: Graph-Theoretic Concepts in Computer Science, Bergen, Norway - On-line coloring of H-free bipartite graphs.
Broersma, H. J., Capponi, A., & Paulusma, D. (2006, May). On-line coloring of H-free bipartite graphs. Presented at 6th Italian Conference on Algorithms and Complexity (CIAC 2006)., Rome, Italy - Matrix and graph orders derived from locally constrained graph homomorphisms
Fiala, J., Paulusma, D., & Telle, J. A. (2023, August). Matrix and graph orders derived from locally constrained graph homomorphisms. Presented at 30th International Symposium on Mathematical Foundations of Computer Science : MFCS 2005, Gdansk, Poland - Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms
Fiala, J., Paulusma, D., & Telle, J. (2005, June). Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. Presented at WG 2005: Graph-Theoretic Concepts in Computer Science, Metz, France - The Computational Complexity of the Minimum Weight Processor Assignment Problem
Broersma, H., Paulusma, D., Smit, G., Vlaardingerbroek, F., & Woeginger, G. (2004, June). The Computational Complexity of the Minimum Weight Processor Assignment Problem. Presented at WG 2004: Graph-Theoretic Concepts in Computer Science, Bad Honnef, Germany - Run-time assignment of tasks to multiple heterogeneous processors
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time assignment of tasks to multiple heterogeneous processors. Presented at 5th PROGRESS Symposium on Embedded Systems., Nieuwegein, The Netherlands - Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. Presented at Proceedings. 2004 IEEE International Conference on Field- Programmable Technology (IEEE Cat. No.04EX921) - The Computational Complexity of the Role Assignment Problem
Fiala, J., & Paulusma, D. (2003, June). The Computational Complexity of the Role Assignment Problem. Presented at ICALP 2003: Automata, Languages and Programming, Eindhoven, The Netherlands - The complexity of graph contractions
Levin, A., Paulusma, D., & Woeginger, G. (2003, June). The complexity of graph contractions. Presented at WG 2003: Graph-Theoretic Concepts in Computer Science, Elspeet, The Netherlands
Journal Article
- Partitioned matching games for international kidney exchange
Benedek, M., Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (online). Partitioned matching games for international kidney exchange. Mathematical Programming, https://doi.org/10.1007/s10107-025-02200-9 - Clique-width for hereditary graph classes
Dabrowski, K., Johnson, M., & Paulusma, D. (online). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002 - Matching Cuts in Graphs of High Girth and H-Free Graphs
Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (online). Matching Cuts in Graphs of High Girth and H-Free Graphs. Algorithmica, https://doi.org/10.1007/s00453-025-01318-8 - Acyclic, star and injective colouring: A complexity picture for H-free graphs
Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662 - Comparing width parameters on graph classes
Brettell, N., Munaro, A., Paulusma, D., & Yang, S. (2025). Comparing width parameters on graph classes. European Journal of Combinatorics, 127, Article 104163. https://doi.org/10.1016/j.ejc.2025.104163 - Computing subset vertex covers in H-free graphs
Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., Rauch, J., & van Leeuwen, E. J. (2025). Computing subset vertex covers in H-free graphs. Theoretical Computer Science, 1032, Article 115088. https://doi.org/10.1016/j.tcs.2025.115088 - Complexity Framework for Forbidden Subgraphs I: The Framework
Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2 - Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius
Lucke, F., Paulusma, D., & Ries, B. (2024). Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius. Theoretical Computer Science, 1017, Article 114795. https://doi.org/10.1016/j.tcs.2024.114795 - Computing balanced solutions for large international kidney exchange schemes
Benedek, M., Biró, P., Paulusma, D., & Ye, X. (2024). Computing balanced solutions for large international kidney exchange schemes. Autonomous Agents and Multi-Agent Systems, 38(1), Article 18. https://doi.org/10.1007/s10458-024-09645-w - An Algorithmic Framework for Locally Constrained Homomorphisms
Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2024). An Algorithmic Framework for Locally Constrained Homomorphisms. SIAM Journal on Discrete Mathematics, 38(2), 1315-1350. https://doi.org/10.1137/22M1513290 - On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2024). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, 117, Article 103821. https://doi.org/10.1016/j.ejc.2023.103821 - Solving problems on generalized convex graphs via mim-width
Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2024). Solving problems on generalized convex graphs via mim-width. Journal of Computer and System Sciences, 140, Article 103493. https://doi.org/10.1016/j.jcss.2023.103493 - Clique‐width: Harnessing the power of atoms
Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2023). Clique‐width: Harnessing the power of atoms. Journal of Graph Theory, 104(4), 769-810. https://doi.org/10.1002/jgt.23000 - The Complexity of L(p, q)-Edge-Labelling
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4 - Finding Matching Cuts in H-Free Graphs
Lucke, F., Paulusma, D., & Ries, B. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, 85(10), 3290-3322. https://doi.org/10.1007/s00453-023-01137-9 - Few induced disjoint paths for H-free graphs
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024 - The Complexity of Matching Games: A Survey
Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281 - Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z - Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034 - Partitioning H-free graphs of bounded diameter
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009 - Computing weighted subset odd cycle transversals in H-free graphs
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. https://doi.org/10.1016/j.jcss.2022.03.002 - QCSP on reflexive tournaments
Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069 - Colouring graphs of bounded diameter in the absence of small cycles
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026 - Hard problems that quickly become very easy
Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213 - Induced disjoint paths in AT-free graphs
Golovach, P., Paulusma, D., & van Leeuwen, E. (2022). Induced disjoint paths in AT-free graphs. Journal of Computer and System Sciences, 124, 170-191. https://doi.org/10.1016/j.jcss.2021.10.003 - Computing subset transversals in H-free graphs
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science, 902, 76-92. https://doi.org/10.1016/j.tcs.2021.12.010 - Disjoint paths and connected subgraphs for H-free graphs
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019 - On the complexity of matching cut for graphs of bounded radius and H-free graphs
Lucke, F., Paulusma, D., & Ries, B. (2022). On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936, 33-42. https://doi.org/10.1016/j.tcs.2022.09.014 - Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs
Paesani, G., Paulusma, D., & Rzążwski, P. (2022). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM Journal on Discrete Mathematics, 36(4), 2453-2472. https://doi.org/10.1137/22m1468864 - Acyclic, Star, and Injective Colouring: Bounding the diameter
Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738 - Bounding the mim-width of hereditary graph classes
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. https://doi.org/10.1002/jgt.22730 - List k-colouring P-free graphs: a mim-width perspective
Brettell, N., Horsfield, J., Munaro, A., & Paulusma, D. (2022). List k-colouring P-free graphs: a mim-width perspective. Information Processing Letters, 173, Article 106168. https://doi.org/10.1016/j.ipl.2021.106168 - Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109. https://doi.org/10.1002/jgt.22683 - Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012 - What graphs are 2-dot product graphs?
Johnson, M., Paulusma, D., & van Leeuwen, E. (2021). What graphs are 2-dot product graphs?. International Journal of Computational Geometry and Applications, 31(01), 1-16. https://doi.org/10.1142/s0218195921500011 - Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852. https://doi.org/10.1007/s00453-020-00747-x - Tree pivot-minors and linear rank-width
Dabrowski, K., Dross, F., Jeong, J., Kante, M., Kwon, O., Oum, S., & Paulusma, D. (2021). Tree pivot-minors and linear rank-width. SIAM Journal on Discrete Mathematics, 35(4), 2922-2945. https://doi.org/10.1137/21m1402339 - Disconnected cuts in claw-free graphs
Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005 - Colouring (Pr + Ps)-Free Graphs
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica, 82(7), 1833-1858. https://doi.org/10.1007/s00453-020-00675-w - Simple games versus weighted voting games: bounding the critical threshold value
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. https://doi.org/10.1007/s00355-019-01221-6 - Clique-width and well-quasi ordering of triangle-free graph classes
Dabrowski, K., Lozin, V., & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences, 108, 64-91. https://doi.org/10.1016/j.jcss.2019.09.001 - Connected vertex cover for (sP1+P5)-free graphs
Johnson, M., Paesani, G., & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica, 82(1), 20-40. https://doi.org/10.1007/s00453-019-00601-9 - Clique-width for graph classes closed under complementation
Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016 - On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Dabrowski, 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. https://doi.org/10.1007/s00453-020-00706-6 - Colouring Square-Free Graphs without Long Induced Paths
Gaspers, S., Huang, S., & Paulusma, D. (2019). Colouring Square-Free Graphs without Long Induced Paths. Journal of Computer and System Sciences, 106, 60-79. https://doi.org/10.1016/j.jcss.2019.06.002 - Filling the complexity gaps for colouring planar and bounded degree graphs
Dabrowski, 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. https://doi.org/10.1002/jgt.22459 - Using contracted solution graphs for solving reconfiguration problems
Bonsma, P., & Paulusma, D. (2019). Using contracted solution graphs for solving reconfiguration problems. Acta Informatica, 56(7-8), 619-648. https://doi.org/10.1007/s00236-019-00336-8 - Bounding clique-width via perfect graphs
Dabrowski, K., Huang, S., & Paulusma, D. (2019). Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, 104, 202-215. https://doi.org/10.1016/j.jcss.2016.06.007 - Hereditary graph classes: when the complexities of coloring and clique cover coincide
Blanché, A., Dabrowski, 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. https://doi.org/10.1002/jgt.22431 - Classifying k-Edge Colouring for H-free Graphs
Galby, E., Lima, P., Paulusma, D., & Ries, B. (2019). Classifying k-Edge Colouring for H-free Graphs. Information Processing Letters, 146, 39-43. https://doi.org/10.1016/j.ipl.2019.02.006 - Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Golovach, P., Heggernes, P., Kratch, D., Lima, P., & Paulusma, D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica, 81(7), 2795-2828. https://doi.org/10.1007/s00453-019-00555-y - On the parameterized complexity of (k,s)-SAT
Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters, 43, 34-36. https://doi.org/10.1016/j.ipl.2018.11.005 - Critical vertices and edges in H-free graphs
Paulusma, D., Picouleau, C., & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257, 361-367. https://doi.org/10.1016/j.dam.2018.08.016 - Surjective H-colouring: New hardness results
Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084 - Surjective H-Colouring over reflexive digraphs
Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431 - Computing square roots of graphs with low maximum degree
Cochefert, M., Couturier, J.-F., Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics, 248, 93-101. https://doi.org/10.1016/j.dam.2017.04.041 - Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs
Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science, 746, 49-72. https://doi.org/10.1016/j.tcs.2018.06.023 - Finding cactus roots in polynomial time
Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2 - Well-quasi-ordering versus clique-width: new results on bigenic classes
Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7 - On colouring (2P2,H)-free and (P5,H)-free graphs
Dabrowski, K., & Paulusma, D. (2018). On colouring (2P2,H)-free and (P5,H)-free graphs. Information Processing Letters, 134, 35-41. https://doi.org/10.1016/j.ipl.2018.02.003 - Independent Feedback Vertex Set for P5-free Graphs
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0474-x - Independent feedback vertex sets for graphs of bounded diameter
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004 - The Stable Fixtures Problem with Payments
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior, 108, 245-268. https://doi.org/10.1016/j.geb.2017.02.002 - Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity
Chiarelli, N., Hartinger, T., 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. https://doi.org/10.1016/j.tcs.2017.09.033 - Contracting Bipartite Graphs to Paths and Cycles
Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013 - Colouring Diamond-free Graphs
Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005 - A linear kernel for finding square roots of almost planar graphs
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008 - A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
Golovach, P., 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. https://doi.org/10.1002/jgt.22028 - Bounding the Clique-Width of H-free Chordal Graphs
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory, 86(1), 42-77. https://doi.org/10.1002/jgt.22111 - The price of connectivity for feedback vertex set
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 B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011 - Graph editing to a fixed target
Golovach, P., Paulusma, D., & Stewart, I. (2017). Graph editing to a fixed target. Discrete Applied Mathematics, 216(Part 1), 181-190. https://doi.org/10.1016/j.dam.2014.07.008 - Kempe equivalence of colourings of cubic graphs
Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008 - A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000 - Editing to a Planar Graph of Given Degrees
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009 - Minimal Disconnected Cuts in Planar Graphs
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696 - The price of connectivity for cycle transversals
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics, 58, 203-224. https://doi.org/10.1016/j.ejc.2016.06.003 - Bounding the clique-width of H-free split graphs
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211, 30-39. https://doi.org/10.1016/j.dam.2016.04.003 - Model counting for CNF formulas of bounded modular treewidth
Paulusma, D., Slivovsky, S., & Szeider, S. (2016). Model counting for CNF formulas of bounded modular treewidth. Algorithmica, 76(1), 168-194. https://doi.org/10.1007/s00453-015-0030-x - Induced disjoint paths in circular-arc graphs in linear time
Golovach, P., Paulusma, D., & van Leeuwen, E. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science, 640, 70-83. https://doi.org/10.1016/j.tcs.2016.06.003 - Finding Shortest Paths Between Graph Colourings
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7 - Clique-width of graph classes defined by two forbidden induced subgraphs
Dabrowski, K. K., & Paulusma, D. (2016). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5), 650-666. https://doi.org/10.1093/comjnl/bxv096 - Editing to Eulerian graphs
Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003 - Classifying the clique-width of H-free bipartite graphs
Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030 - Parameterized algorithms for finding square roots
Cochefert, M., Couturier, J.-. F., Golovach, P. A., & Paulusma, D. (2016). Parameterized algorithms for finding square roots. Algorithmica, 74(2), 602-629. https://doi.org/10.1007/s00453-014-9967-4 - Narrowing the complexity gap for colouring (Cs, Pt)-free graphs
Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039 - Knocking out P_k-free graphs
Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010 - Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
Broersma, H., Fiala, J., Golovach, P., 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. https://doi.org/10.1002/jgt.21832 - Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028 - Modifying a Graph Using Vertex Elimination
Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2 - Algorithms for diversity and clustering in social networks through dot product graphs
Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001 - The computational complexity of disconnected cut and 2K2-partition
Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002 - Coloring graphs characterized by a forbidden subgraph
Golovach, P., Paulusma, D., & Ries, B. (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics, 180, 101-110. https://doi.org/10.1016/j.dam.2014.08.008 - Induced disjoint paths in claw-free graphs
Golovach, P., Paulusma, D., & van Leeuwen, E. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics, 29(1), 348-375. https://doi.org/10.1137/140963200 - List Coloring in the Absence of a Linear Forest
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0 - Closing complexity gaps for coloring problems on H-free graphs
Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004 - Parameterized complexity of three edge contraction problems with degree constraints
Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2014). Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51(7), 473-497. https://doi.org/10.1007/s00236-014-0204-z - Detecting fixed patterns in chordal graphs in polynomial time
Belmonte, R., Golovach, P., 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. https://doi.org/10.1007/s00453-013-9748-5 - Solutions for the stable roommates problem with payments
Biró, P., Bomhoff, M., Golovach, P., Kern, W., & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science, 540-541, 53-61. https://doi.org/10.1016/j.tcs.2013.03.027 - Packing bipartite graphs with covers of complete bipartite graphs
Chalopin, J., & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168, 40-50. https://doi.org/10.1016/j.dam.2012.08.026 - Coloring graphs without short cycles and long induced paths
Golovach, P., Paulusma, D., & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167, 107-120. https://doi.org/10.1016/j.dam.2013.12.008 - List coloring in the absence of two subgraphs
Golovach, P., & Paulusma, D. (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166, 123-130. https://doi.org/10.1016/j.dam.2013.10.010 - Obtaining Online Ecological Colourings by Generalizing First-Fit
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. https://doi.org/10.1007/s00224-013-9513-9 - Colouring of graphs with Ramsey-type forbidden subgraphs
Dabrowski, K., Golovach, P., & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522, 34-43. https://doi.org/10.1016/j.tcs.2013.12.004 - Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
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. https://doi.org/10.1007/s10878-012-9490-y - Lift-contractions
Golovach, P., Paulusma, D., Kaminski, M., & Thilikos, D. (2014). Lift-contractions. European Journal of Combinatorics, 35, 286-296. https://doi.org/10.1016/j.ejc.2013.06.026 - Characterizing graphs of small carving-width
Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036 - Detecting induced minors in AT-free graphs
Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029 - Satisfiability of acyclic and almost acyclic CNF formulas
Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039 - Three complexity results on coloring Pk-free graphs
Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008 - Increasing the minimum degree of a graph by contractions
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030 - Obtaining planarity by contracting few edges
Golovach, P., van 't Hof, P., & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science, 476, 38-46. https://doi.org/10.1016/j.tcs.2012.12.041 - Choosability on H-free graphs
Golovach, P., Heggernes, P., van 't Hof, P., & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters, 113(4), 107-110. https://doi.org/10.1016/j.ipl.2012.12.003 - A note on contracting claw-free graphs
Fiala, J., Kaminski, M., & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2), 223-232 - 4-Coloring H-free graphs when H is small
Golovach, P., Paulusma, D., & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics, 161(1-2), 140-150. https://doi.org/10.1016/j.dam.2012.08.022 - Exact algorithms for finding longest cycles in claw-free graphs
Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4 - Detecting induced star-like minors in polynomial time
Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002 - Computing vertex-surjective homomorphisms to partially reflexive trees
Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039 - Finding vertex-surjective graph homomorphisms
Golovach, P., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica, 49(6), 381-394. https://doi.org/10.1007/s00236-012-0164-0 - On the parameterized complexity of coloring graphs in the absence of a linear forest
Couturier, J., Golovach, P., 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. https://doi.org/10.1016/j.jda.2012.04.008 - Computing role assignments of proper interval graphs in polynomial time
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. https://doi.org/10.1016/j.jda.2011.12.004 - Distance three labelings of trees
Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004 - On graph contractions and induced minors
Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005 - Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076 - Induced packing of odd cycles in planar graphs
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004 - The k-in-a-path problem for claw-free graphs
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. https://doi.org/10.1007/s00453-010-9468-z - Finding induced paths of given parity in claw-free graphs
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. https://doi.org/10.1007/s00453-010-9470-5 - Updating the complexity status of coloring graphs without a fixed induced linear forest
Broersma, H., Golovach, P., 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. https://doi.org/10.1016/j.tcs.2011.10.005 - Computing solutions for matching games
Biro, P., Kern, W., & Paulusma, D. (2012). Computing solutions for matching games. International Journal of Game Theory, 41(1), 75-90. https://doi.org/10.1007/s00182-011-0273-y - Containment relations in split graphs
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Containment relations in split graphs. Discrete Applied Mathematics, 160(1-2), 155-163. https://doi.org/10.1016/j.dam.2011.10.004 - On partitioning a graph into two connected subgraphs
Paulusma, D., & Rooij van, J. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science, 412(48), 6761-6769. https://doi.org/10.1016/j.tcs.2011.09.001 - Parameterizing cut sets in a graph by the number of their components
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science, 412(45), 6340-6350. https://doi.org/10.1016/j.tcs.2011.07.005 - Graph labelings derived from models in distributed computing: a complete complexity classification
Chalopin, J., & Paulusma, D. (2011). Graph labelings derived from models in distributed computing: a complete complexity classification. Networks, 58(3), 207-231. https://doi.org/10.1002/net.20432 - Contracting planar graphs to contractions of triangulations
Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010 - On disconnected cuts and separators
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027 - Computing role assignments of chordal graphs
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041 - Computing sharp 2-factors in claw-free graphs
Broersma, H., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. https://doi.org/10.1016/j.jda.2009.07.001 - Path factors and parallel knock-out schemes of almost claw-free graphs
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. https://doi.org/10.1016/j.disc.2009.04.022 - Comparing universal covers in polynomial time
Fiala, J., & Paulusma., D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems, 46(4), 620-635. https://doi.org/10.1007/s00224-009-9200-z - A new characterization of P6-free graphs
Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025 - Partitioning graphs into connected parts
Hof, P. V. '., Paulusma, D., & Woeginger, G. J. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028 - Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs
Broersma, H., 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. https://doi.org/10.1007/s00373-009-0855-7 - On the core and f-nucleolus of flow games
Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405 - λ-backbone colorings along pairwise disjoint stars and matchings
Broersma, H., Fujisawa, J., Marchal, L., Paulusma, D., Salman, A., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007 - Covering graphs with few complete bipartite subgraphs
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059 - Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (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. https://doi.org/10.7151/dmgt.1437 - Upper bounds and algorithms for parallel knock-out numbers
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024 - The computational complexity of graph contractions II: two tough polynomially solvable cases
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52(1), 32-56. https://doi.org/10.1002/net.20249 - Locally constrained graph homomorphisms and equitable partitions
Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006 - The computational complexity of graph contractions I: polynomially solvable and NP-complete cases
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51(3), 178-189. https://doi.org/10.1002/net.20214 - Relative length of longest paths and longest cycles in triangle-free graphs
Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070 - The computational complexity of the parallel knock-out problem
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021 - A new algorithm for on-line coloring bipartite graphs
Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675 - Cycles through specified vertices in triangle-free graphs
Paulusma, D., & Yoshimito, K. (2007). Cycles through specified vertices in triangle-free graphs. Discussiones Mathematicae. Graph Theory, 27(1), 179-191. https://doi.org/10.7151/dmgt.1354 - A complete complexity classification of the role assignment problem
Fiala, J., & Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1), 67-81. https://doi.org/10.1016/j.tcs.2005.09.029 - The computational complexity of the elimination problem in generalized sports competitions
Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003 - Matching games : the least core and the nucleolus
Kern, W., & Paulusma, D. (2003). Matching games : the least core and the nucleolus. Mathematics of Operations Research, 28(2), 294-308. https://doi.org/10.1287/moor.28.2.294.14477 - Two extensions of the Shapley value for cooperative games
Driessen, T., & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research, 53(1), 35-49. https://doi.org/10.1007/s001860000099 - The new FIFA rules are hard: complexity aspects of sports competitions
Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9 - Note on the computational complexity of least core concepts for min-cost spanning tree games
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. https://doi.org/10.1007/s001860000059
Report
- New Bounds for the Snake-in-the-Box Problem
Allison, D., & Paulusma, D. (2019). New Bounds for the Snake-in-the-Box Problem. [No known commissioning body] - On Finding Paths Passing through Specified Vertices
Paulusma, D. (2011). On Finding Paths Passing through Specified Vertices. [No known commissioning body]
Supervision students
Tala Eagling-Vose
Postgraduate Student
Xin Ye
Postgraduate Student
Yilin Li
Postgraduate Student