Skip to main content

Staff profile

Overview

Professor Matthew Johnson

Head of Department

Affiliations
AffiliationTelephone
Head of Department in the Department of Computer Science+44 (0) 191 33 41747

Biography

Matthew Johnson is a Professor in Computer Science at Durham University. He is a member of the Algorithms and Complexity research group and his research interests include algorithmic graph theory, combinatorial optimization and combinatorial designs. For further information, including a publications list with links to preprints and unpublished articles, see his personal web page. (The content below is generated semi-automatically and more difficult to control.)

Research interests

  • Combinatorial Reconfiguration
  • Graph Partitioning
  • Graph Theory

Publications

Chapter in book

  • A multi-level hypergraph partitioning algorithm using rough set clustering
    Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings. (pp. 159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

Conference Paper

  • Complexity framework for forbidden subgraphs IV: The Steiner Forest problem
    Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Lecture Notes in Computer Science, 14764, 206-217. https://doi.org/10.1007/978-3-031-63021-7_16
  • 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). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) (pp. 29:1-29:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SWAT.2024.29
  • 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). Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded. In Proceedings of AAMAS-2024 (pp. 2153-2155).
  • 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). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (pp. 57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
  • Computing weighted subset transversals in H-free graphs
    Brettell, N., Johnson, M., & Paulusma, D. (2021). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (pp. 229-242). Springer Verlag. https://doi.org/10.1007/978-3-030-83508-8_17
  • Steiner trees for hereditary graph classes
    Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2021). Steiner trees for hereditary graph classes. In Y. Kohayakawa & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (pp. 613-624). Springer Verlag. https://doi.org/10.1007/978-3-030-61792-9_48
  • Computing subset transversals in H-free graphs
    Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020). Computing subset transversals in H-free graphs. In I. Adler & H. Müller (Eds.), WG 2020: Graph-Theoretic Concepts in Computer Science (pp. 187-199). Springer Verlag. https://doi.org/10.1007/978-3-030-60440-0_15
  • Independent transversals versus transversals
    Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, July 29). 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). On cycle transversals and their connected variants in the absence of a small linear forest. In L. A. Gąsieniec, J. Jansson, & C. Levcopoulos (Eds.), Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings. (pp. 258-273). Springer Verlag. https://doi.org/10.1007/978-3-030-25027-0_18
  • Finding a small number of colourful components
    Bulteau, L., Dabrowski, K., Fertin, G., Johnson, M., Paulusma, D., & Vialette, S. (2019). Finding a small number of colourful components. In 30th Annual Symposium on Combinatorial Pattern Matching. Schloss Dagstuhl.
  • Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
    Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. In Z. Friggstad, J.-R. Sack, & M. R. Salavatipour (Eds.), Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings. (pp. 181-195). Springer Verlag. https://doi.org/10.1007/978-3-030-24766-9_14
  • Connected Vertex Cover for (sP1+P5)-free graphs
    Johnson, M., Paesani, G., & Paulusma, D. (2018). Connected Vertex Cover for (sP1+P5)-free graphs. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings. (pp. 279-291). Springer Verlag. https://doi.org/10.1007/978-3-030-00256-5_23
  • 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). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). (pp. 63:1-63:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2018.63
  • Clique-Width for Graph Classes Closed under Complementation
    Blanché A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation. In K. G. Larsen, H. L. Bodlaender, & J.-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.73
  • Recognizing Graphs Close to Bipartite Graphs
    Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Recognizing Graphs Close to Bipartite Graphs. In K. G. Larsen, H. L. Bodlaender, & J.-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.70
  • Surjective H-Colouring: new hardness results
    Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017). Surjective H-Colouring: new hardness results. In J. Kari, F. Manea, & I. Petre (Eds.), Unveiling dynamics an complexity. (pp. 270-281). Springer Verlag. https://doi.org/10.1007/978-3-319-58741-7_26
  • Independent Feedback Vertex Set for P5-free Graphs
    Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent Feedback Vertex Set for P5-free Graphs. In Y. Okamoto & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings. (pp. 16:1-16:12). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/lipics.isaac.2017.16
  • Filling the complexity gaps for colouring planar and bounded degree graphs
    Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers. (pp. 100-111). Springer Verlag. https://doi.org/10.1007/978-3-319-29516-9_9
  • Kempe equivalence of colourings of cubic graphs
    Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. In Electronic Notes in Discrete Mathematics (pp. 243-249). Elsevier. https://doi.org/10.1016/j.endm.2015.06.034
  • What graphs are 2-dot product graphs?
    Johnson, M., van Leeuwen, E., & Paulusma, D. (2015). What graphs are 2-dot product graphs?. In Electronic Notes in Discrete Mathematics (pp. 705-711). Elsevier. https://doi.org/10.1016/j.endm.2015.06.095
  • The price of connectivity for cycle transversals
    Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015). The price of connectivity for cycle transversals. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II. (pp. 395-406). Springer Verlag. https://doi.org/10.1007/978-3-662-48054-0_33
  • Obtaining online ecological colourings by generalizing first-fit
    Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. In F. Ablayev & E. W. Mayr (Eds.), Computer science : theory and applications : 5th International Computer Science Symposium in Russia, CSR, 16-20 June 2010, Kazan, Russia ; proceedings. (pp. 240-251). Springer Verlag. https://doi.org/10.1007/978-3-642-13182-0_22
  • The computational complexity of the parallel knock-out problem
    Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006). The computational complexity of the parallel knock-out problem. In LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings. (pp. 250-261). Springer Verlag. https://doi.org/10.1007/11682462_26
  • The External Network Problem with edge- or arc-connectivity requirements
    van den Heuvel, J., & Johnson, M. (2005). The External Network Problem with edge- or arc-connectivity requirements. In A. López-Ortiz & A. Hamel (Eds.), Combinatorial and algorithmic aspects of networking : first workshop on combinatorial and algorithmic aspects of networking, CAAN 2004, Banff, Alberta, Canada, August 5-7, 2004 ; revised selected papers. (pp. 114-126). Springer Verlag. https://doi.org/10.1007/11527954_11

Journal Article

Supervision students

David Fairbairn

3P

Xin Ye

Postgraduate Student