Staff profile

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.)

• Graph Theory
• Combinatorial Reconfiguration
• Graph Partitioning

• ACiD: Algorithms and Complexity

Chapter in book

• Lotfifar, Foad & Johnson, Matthew (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In Euro-Par 2015: Parallel Processing: 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings. Träff, Jesper, Hunold, Sascha & Versaci, Francesco Heidelberg: Springer. 9233: 159-170.

Conference Paper

• Brettell, N., Johnson, M., Paesani, G. & Paulusma, D. (2020), Computing subset transversals in H-free graphs, in Adler, I. & Müller, H. eds, Lecture Notes in Computer Science 12301: WG 2020. Leeds, England, Springer, 187-199.
• Dabrowski, K.K., Johnson, M., Paesani, G. Paulusma, D. & Zamaraev, V. (2019), Independent transversals versus transversals, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 585-591.
• Bonamy, M., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019), Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy, in Friggstad, Zachary Sack, Jörg-Rüdiger & Salavatipour, Mohammad R. eds, Lecture Notes in Computer Science 11646: WADS 2019. Edmonton, Canada, Springer, Cham, 181-195.
• Feghali, C. Johnson, M., Paesani, G. & Paulusma, D. (2019), On cycle transversals and their connected variants in the absence of a small linear forest, in Gąsieniec, Leszek Antoni Jansson, Jesper & Levcopoulos, Christos eds, Lecture Notes in Computer Science 11651: FCT 2019. Copenhagen, Denmark, Springer, Cham, 258-273.
• 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.
• 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.
• 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.
• Blanché, A., Dabrowski, K.K., Johnson, M., Lozin, V.V., Paulusma, D. & Zamaraev, V. (2017), Clique-Width for Graph Classes Closed under Complementation, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Aalborg, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 73.
• Dabrowski, K.K., 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.
• 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.
• 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., 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.

Journal Article

• Johnson, M., Paesani, G. & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica 82(1): 20-40.
• Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019). Clique-width for hereditary graph classes. London Mathematical Society Lecture Note Series 1-56.
• Dabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory 92(4): 377-393.
• Golovach, P.A., Johnson, M., Martin, B., Paulusma, D. & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability 8(1): 27-42.
• Bonamy, Marthe, Bousquet, Nicolas, Feghali, Carl & Johnson, Matthew (2019). On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Journal of Combinatorial Theory, Series B 135: 179-199.
• Blanché, A., Dabrowski, K.K., Johnson, M. & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory 91(3): 267-289.
• Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2019). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica 81(4): 1342-1369.
• Feghali, Carl, Johnson, Matthew & Thomas, Daniel (2018). Erdős–Ko–Rado theorems for a family of trees. Discrete Applied Mathematics 236: 464-471.
• Feghali, Carl & Johnson, Matthew (2018). Enclosings of decompositions of complete multigraphs in 2-factorizations. Journal of Combinatorial Designs 26(5): 205-218.
• Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters 131: 26-32.
• Golovach, P.A., Johnson, M., Paulusma, D. & Song. J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory 84(4): 331-363.
• Feghali, C., Johnson, M. & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics 59: 1-10.
• Hartinger, T.R., Johnson, M., Milanič, M. & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics 58: 203-224.
• Mäsker, M., Nagel, L., Brinkmann, A., Lotfifar, F. & Johnson, M. (2016). Smart grid-aware scheduling in data centres. Computer Communications 96: 73-85.
• Feghali, C., Johnson, M. & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory 83(4): 340-358.
• Johnson, M., Kratsch, D., Kratsch, S., Patel, V. & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica 75(2): 295-321.
• Huang, S., Johnson, M. & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal 58(11): 3074-3088.
• Johnson, M., Paulusma, D. & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics 190-191: 100-108.
• Johnson, M., Paulusma, D. & van Leeuwen, E.J. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks 41: 48-55.
• 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
• Cereceda, Luis, van den Heuvel, Jan & Johnson, Matthew (2011). Finding paths between 3-colorings. Journal of Graph Theory 67(1): 69-82.
• Cereceda, Luis, van den Heuvel, Jan & Johnson, Matthew (2009). Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics 30(7): 1593-1606.
• Broersma, H.J., Johnson, M. & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science 410(14): 1319-1327.
• Cereceda, Luis, van den Heuvel, Jan & Johnson, Matthew (2008). Connectedness of the graph of vertex-colourings. Discrete Mathematics 308(5-6): 913-919.
• Heuvel van den, Jan & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks 51(2): 113-119.
• Johnson, M. (2007). Amalgamations of factorizations of complete graphs. Journal of Combinatorial Theory, Series B 97(4): 597-611.
• Bonsma, Paul Cereceda, Luis van den Heuvel, Jan & Johnson, Matthew (2007). Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electronic Notes in Discrete Mathematics 29: 463-469.
• Cereceda, Luis, van den Heuvel, Jan & Johnson, Matthew (2007). Mixing 3-colourings in bipartite graphs. Lecture Notes in Computer Science 4769: 166-177.
• Hilton, A. J. W. & Johnson, Matthew (2006). Cycle decompositions of the complete graph. Ars Combinatoria 81: 311-324.
• Eslachi, Ch. & Johnson, Matthew (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory 45(2): 81-100.
• Hilton, A. J. W. & Johnson, Matthew. (2004). Amalgamations of factorizations of complete equipartite graphs. Discrete Mathematics 284(1-3): 157-175.
• Hilton, A. J. W., Johnson, Matthew., Rodger, C. A. & Wantland, E. B. (2003). Amalgamations of connected k-factorizations. Journal of Combinatorial Theory Series B 88(2): 267-279.
• Hilton, A. J. W. & Johnson, Matthew. (2003). An algorithm for finding factorizations of complete graphs. Journal of Graph Theory 43: 132-136.