Cookies

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

Durham University

Computer Science

Profile

Professor Matthew Johnson, BSc PhD

Personal web page

Telephone: +44 (0) 191 33 41747
Room number: E251

(email at matthew.johnson2@durham.ac.uk)

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.

Research Groups

  • Algorithms and Complexity

Research Interests

  • Combinatorial Reconfiguration
  • Graph Partitioning
  • Graph Theory

Publications

Journal Article

Chapter in book

Conference Paper

  • Bonamy, M., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019), Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy, in Friggstad, Zachary Sack, Jörg-Rüdiger & Salavatipour, Mohammad R. eds, Lecture Notes in Computer Science 11646: WADS 2019. Edmonton, Canada, Springer, Cham, 181-195.
  • Dabrowski, K.K., Johnson, M., Paesani, G. , Paulusma, D. & Zamaraev, V. (2019), Independent transversals versus transversals, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 585-591.
  • Feghali, C. Johnson, M., Paesani, G. & Paulusma, D. (2019), On cycle transversals and their connected variants in the absence of a small linear forest, in Gąsieniec, Leszek Antoni Jansson, Jesper & Levcopoulos, Christos eds, Lecture Notes in Computer Science 11651: FCT 2019. Copenhagen, Denmark, Springer, Cham, 258-273.
  • Dabrowski, K.K., Johnson, M., Paesani, G., Paulusma, D. & Zamaraev, V. (2018), On the price of independence for vertex cover, feedback vertex set and odd cycle transversal, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics 117: 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 63:1--63:15.
  • Blanché, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D. & Zamaraev, V. (2017), Clique-Width for Graph Classes Closed under Complementation, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 73.
  • Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2017), Independent Feedback Vertex Set for P5-free Graphs, in Okamoto, Yoshio & Tokuyama, Takeshi eds, Leibniz International Proceedings in Informatics 92: ISAAC 2017. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 16:1-16:12.
  • Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2017), Recognizing Graphs Close to Bipartite Graphs, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 70.
  • Golovach, P. A., Johnson, M., Martin, M., Paulusma, D. & Stewart, A. (2017), Surjective H-Colouring: new hardness results, in Kari J., Manea F. & Petre I. eds, Lecture Notes in Computer Science 10307: Computability in Europe (CiE 2017). Turku, Finland, Springer, Cham, 270-281.
  • Dabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2016), Filling the complexity gaps for colouring planar and bounded degree graphs, in Lipták, Zsuzsanna & Smyth, William F. eds, Lecture Notes in Computer Science 9538: 26th International Workshop on Combinatorial Algorithms (IWOCA 2015). Verona, Italy, Springer, 100-111.
  • Feghali, C., Johnson, M. & Paulusma, D. (2015), Kempe equivalence of colourings of cubic graphs, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Bergen, 243-249.
  • Hartinger, T.R., Johnson, M., Milanič, M. & Paulusma, D. (2015), The price of connectivity for cycle transversals, Lecture Notes in Computer Science 9235: 40th International Symposium, MFCS 2015. Milan, Italy, Springer, Milan, 395-406.
  • Johnson, M., van Leeuwen, E.J. & Paulusma, D. (2015), What graphs are 2-dot product graphs?, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Elsevier, Bergen, 705-711.
  • Johnson, M., Patel, V., Paulusma, D. & Trunck, T. (2010), Obtaining online ecological colourings by generalizing first-fit, 6072: 5th International Computer Science Symposium in Russia (CSR 2010). Springer, 240-251.
  • Broersma, H., Johnson, M., Paulusma, D. & Stewart, I.A. (2006), The computational complexity of the parallel knock-out problem, Lecture Notes in Computer Science 3887: 7th Latin American Theoretical Informatics Symposium (LATIN 2006). Valdivia, Chile., Springer, Berlin, 250-261.
  • van den Heuvel, Jan & Johnson, Matthew (2005), The External Network Problem with edge- or arc-connectivity requirements, in López-Ortiz, A. & Hamel, A. eds, Lecture Notes in Computer Science 3405: Combinatorial and Algorithmic Aspects of Networking (CAAN 2004). Banff, Springer, Berlin, 114-126.

Supervises