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

• Combinatorial Reconfiguration
• Graph Partitioning
• Graph Theory

Chapter in book

• 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 (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

Conference Paper

• 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
• Brettell, N., Johnson, M., & Paulusma, D. (2021, August). Computing weighted subset transversals in H-free graphs. Presented at WADS 2021, Halifax, Nova Scotia
• 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
• Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020, December). Computing subset transversals in H-free graphs. Presented at WG 2020, Leeds, England
• Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• van den Heuvel, J., & Johnson, M. (2004, August). The External Network Problem with edge- or arc-connectivity requirements. Presented at Combinatorial and Algorithmic Aspects of Networking (CAAN 2004), Banff, Alberta, Canada

Journal Article

• Dabrowski, K., Johnson, M., & Paulusma, D. (online). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002
• Cereceda, L., van den Heuvel, J., & Johnson, M. (online). Mixing 3-colourings in bipartite graphs. Lecture Notes in Computer Science, 166-177. https://doi.org/10.1007/978-3-540-74839-7_17
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Bonamy, M., Bousquet, N., Feghali, C., & Johnson, M. (2019). On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Journal of Combinatorial Theory, Series B, 135, 179-199. https://doi.org/10.1016/j.jctb.2018.08.002
• 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
• 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
• Feghali, C., & Johnson, M. (2018). Enclosings of decompositions of complete multigraphs in 2-factorizations. Journal of Combinatorial Designs, 26(5), 205-218. https://doi.org/10.1002/jcd.21601
• 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
• Feghali, C., Johnson, M., & Thomas, D. (2018). Erdős–Ko–Rado theorems for a family of trees. Discrete Applied Mathematics, 236, 464-471. https://doi.org/10.1016/j.dam.2017.10.009
• 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
• 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
• Mäsker, M., Nagel, L., Brinkmann, A., Lotfifar, F., & Johnson, M. (2016). Smart grid-aware scheduling in data centres. Computer Communications, 96, 73-85. https://doi.org/10.1016/j.comcom.2016.04.021
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Cereceda, L., van den Heuvel, J., & Johnson, M. (2011). Finding paths between 3-colorings. Journal of Graph Theory, 67(1), 69-82. https://doi.org/10.1002/jgt.20514
• Cereceda, L., van den Heuvel, J., & Johnson, M. (2009). Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7), 1593-1606. https://doi.org/10.1016/j.ejc.2009.03.011
• 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
• Cereceda, L., van den Heuvel, J., & Johnson, M. (2008). Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5-6), 913-919. https://doi.org/10.1016/j.disc.2007.07.028
• Heuvel van den, J., & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2), 113-119. https://doi.org/10.1002/net.20206
• Bonsma, P., Cereceda, L., van den Heuvel, J., & Johnson, M. (2007). Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electronic Notes in Discrete Mathematics, 29, 463-469. https://doi.org/10.1016/j.endm.2007.07.073
• Johnson, M. (2007). Amalgamations of factorizations of complete graphs. Journal of Combinatorial Theory, Series B, 97(4), 597-611. https://doi.org/10.1016/j.jctb.2006.09.004
• Hilton, A., & Johnson, M. (2006). Cycle decompositions of the complete graph. Ars combinatoria, 81, 311-324
• Hilton, A., & Johnson, M. (2004). Amalgamations of factorizations of complete equipartite graphs,. Discrete Mathematics, 284(1-3), 157-175. https://doi.org/10.1016/j.disc.2003.11.030
• Eslachi, C., & Johnson, M. (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory, 45(2), 81-100. https://doi.org/10.1002/jgt.10154
• Hilton, A., Johnson, M., Rodger, C., & Wantland, E. (2003). Amalgamations of connected k-factorizations. Journal of Combinatorial Theory, Series B, 88(2), 267-279. https://doi.org/10.1016/s0095-8956%2803%2900030-3
• Hilton, A., & Johnson, M. (2003). An algorithm for finding factorizations of complete graphs,. Journal of Graph Theory, 43, 132-136. https://doi.org/10.1002/jgt.10109