Matthew Johnson

According to our database, Matthew Johnson authored at least 81 papers between 2001 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.

Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev

Eur. J. Comb., March, 2024

Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs.

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.

Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the Combinatorial Algorithms - 35th International Workshop, 2024

Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded.

Márton Benedek, Péter Biró, Gergely Csáji, Matthew Johnson, Daniël Paulusma, Xin Ye

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, 2024

2023

The Complexity of Matching Games: A Survey.

Márton Benedek, Péter Biró, Matthew Johnson, Daniël Paulusma, Xin Ye

J. Artif. Intell. Res., 2023

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs.

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

Computing subset transversals in <i>H</i>-free graphs.

Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Theor. Comput. Sci., 2022

Computing Weighted Subset Odd Cycle Transversals in <i>H</i>-free graphs.

Nick Brettell, Matthew Johnson, Daniël Paulusma

J. Comput. Syst. Sci., 2022

Complexity Framework For Forbidden Subgraphs.

Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

CoRR, 2022

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs.

Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen

CoRR, 2022

2021

Steiner trees for hereditary graph classes: A treewidth perspective.

Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen

Theor. Comput. Sci., 2021

Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration.

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

J. Graph Theory, 2021

What Graphs are 2-Dot Product Graphs?

Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen

Int. J. Comput. Geom. Appl., 2021

Graph Isomorphism for (H_{1, H₂₎}-Free Graphs: An Almost Complete Dichotomy.

Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron

Algorithmica, 2021

Computing Weighted Subset Transversals in H-Free Graphs.

Nick Brettell, Matthew Johnson, Daniël Paulusma

Proceedings of the Algorithms and Data Structures - 17th International Symposium, 2021

Preface.

Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, Daniël Paulusma

Proceedings of the Surveys in Combinatorics, 2021

2020

Clique-Width for Graph Classes Closed under Complementation.

Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, Viktor Zamaraev

SIAM J. Discret. Math., 2020

Connected Vertex Cover for (sP_1+P₅₎-Free Graphs.

Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Algorithmica, 2020

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Pawel Rzazewski

Algorithmica, 2020

Computing Subset Transversals in H-Free Graphs.

Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Steiner Trees for Hereditary Graph Classes.

Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

2019

Filling the complexity gaps for colouring planar and bounded degree graphs.

Konrad K. Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma

J. Graph Theory, 2019

Hereditary graph classes: When the complexities of coloring and clique cover coincide.

Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma

J. Graph Theory, 2019

On a conjecture of Mohar concerning Kempe equivalence of regular graphs.

Marthe Bonamy, Nicolas Bousquet, Carl Feghali, Matthew Johnson

J. Comb. Theory B, 2019

Report on BCTCS & AlgoUK 2019.

Matthew Johnson, Barnaby Martin, George B. Mertzios, Daniël Paulusma

Bull. EATCS, 2019

Surjective H-colouring: New hardness results.

Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart

Comput., 2019

Independent Feedback Vertex Set for P₅-Free Graphs.

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

Algorithmica, 2019

Graph Isomorphism for (H₁, H₂)-Free Graphs: An Almost Complete Dichotomy.

Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

Finding a Small Number of Colourful Components.

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, Stéphane Vialette

Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

Clique-width for hereditary graph classes.

Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma

Proceedings of the Surveys in Combinatorics, 2019: Invited lectures from the 27th British Combinatorial Conference, Birmingham, UK, July 29, 2019

2018

Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.

Nina Chiarelli, Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma

Theor. Comput. Sci., 2018

Independent feedback vertex sets for graphs of bounded diameter.

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

Inf. Process. Lett., 2018

Erdős-Ko-Rado theorems for a family of trees.

Carl Feghali, Matthew Johnson, Daniel Thomas

Discret. Appl. Math., 2018

Connected Vertex Cover for (sP_1+P_5) ( s P 1 + P 5 ) -Free Graphs.

Matthew Johnson, Giacomo Paesani, Daniël Paulusma

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

2017

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.

Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song

J. Graph Theory, 2017

Connected Vertex Cover for (sP₁+P₅)-Free Graphs.

Matthew Johnson, Giacomo Paesani, Daniël Paulusma

CoRR, 2017

Recognizing Graphs Close to Bipartite Graphs.

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Independent Feedback Vertex Set for P_5-free Graphs.

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences.

Carl Feghali, Matthew Johnson, Daniël Paulusma

J. Graph Theory, 2016

The price of connectivity for cycle transversals.

Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma

Eur. J. Comb., 2016

A Serial Multilevel Hypergraph Partitioning Algorithm.

Foad Lotfifar, Matthew Johnson

CoRR, 2016

Colouring on Hereditary Graph Classes Closed under Complementation.

Alexandre Blanché, Konrad Kazimierz Dabrowski, Matthew Johnson, Daniël Paulusma

CoRR, 2016

Smart Grid-aware scheduling in data centres.

Markus Mäsker, Lars Nagel, André Brinkmann, Foad Lotfifar, Matthew Johnson

Comput. Commun., 2016

Finding Shortest Paths Between Graph Colourings.

Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma

Algorithmica, 2016

2015

Algorithms for diversity and clustering in social networks through dot product graphs.

Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen

Soc. Networks, 2015

Kempe Equivalence of Colourings of Cubic Graphs.

Carl Feghali, Matthew Johnson, Daniël Paulusma

Electron. Notes Discret. Math., 2015

Knocking out _P_k-free graphs.

Matthew Johnson, Daniël Paulusma, Anthony Stewart

Discret. Appl. Math., 2015

Narrowing the Complexity Gap for Colouring (<i>C_s, P_t</i>)-Free Graphs.

Shenwei Huang, Matthew Johnson, Daniël Paulusma

Comput. J., 2015

A Multi-level Hypergraph Partitioning Algorithm Using Rough Set Clustering.

Foad Lotfifar, Matthew Johnson

Proceedings of the Euro-Par 2015: Parallel Processing, 2015

2014

Obtaining Online Ecological Colourings by Generalizing First-Fit.

Matthew Johnson, Viresh Patel, Daniël Paulusma, Théophile Trunck

Theory Comput. Syst., 2014

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma

J. Comb. Optim., 2014

Narrowing the Complexity Gap for Colouring ($C_s$, $P_t$)-Free Graphs.

Shenwei Huang, Matthew Johnson, Daniël Paulusma

CoRR, 2014

A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs.

Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song

CoRR, 2014

Colouring Reconfiguration Is Fixed-Parameter Tractable.

Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma

CoRR, 2014

Knocking Out P k -free Graphs.

Matthew Johnson, Daniël Paulusma, Anthony Stewart

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

A Reconfigurations Analogue of Brooks' Theorem.

Carl Feghali, Matthew Johnson, Daniël Paulusma

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Narrowing the Complexity Gap for Colouring (C s , P t )-Free Graphs.

Shenwei Huang, Matthew Johnson, Daniël Paulusma

Proceedings of the Algorithmic Aspects in Information and Management, 2014

2013

Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs.

Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012

Editorial.

Iain A. Stewart, Daniël Paulusma, Matthew Johnson

J. Discrete Algorithms, 2012

2011

Finding paths between 3-colorings.

Luis Cereceda, Jan van den Heuvel, Matthew Johnson

J. Graph Theory, 2011

On the diameter of reconfiguration graphs for vertex colourings.

Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma

Electron. Notes Discret. Math., 2011

2010

Editorial.

Hajo Broersma, Stefan S. Dantchev, Matthew Johnson, Stefan Szeider

J. Discrete Algorithms, 2010

Path factors and parallel knock-out schemes of almost claw-free graphs.

Matthew Johnson, Daniël Paulusma, Chantal Wood

Discret. Math., 2010

2009

Upper bounds and algorithms for parallel knock-out numbers.

Hajo Broersma, Matthew Johnson, Daniël Paulusma

Theor. Comput. Sci., 2009

Mixing 3-colourings in bipartite graphs.

Luis Cereceda, Jan van den Heuvel, Matthew Johnson

Eur. J. Comb., 2009

2008

The computational complexity of the parallel knock-out problem.

Hajo Broersma, Matthew Johnson, Daniël Paulusma, Iain A. Stewart

Theor. Comput. Sci., 2008

Transversals of subtree hypergraphs and the source location problem in digraphs.

Jan van den Heuvel, Matthew Johnson

Networks, 2008

Preface.

Hajo Broersma, Stefan S. Dantchev, Matthew Johnson, Stefan Szeider

J. Discrete Algorithms, 2008

Connectedness of the graph of vertex-colourings.

Luis Cereceda, Jan van den Heuvel, Matthew Johnson

Discret. Math., 2008

Finding Paths Between 3-Colourings.

Matthew Johnson, Luis Cereceda, Jan van den Heuvel

Proceedings of the 19th International Workshop on Combinatorial Algorithms, 2008

2007

Amalgamations of factorizations of complete graphs.

Matthew Johnson

J. Comb. Theory B, 2007

Finding Paths between Graph Colourings: Computational Complexity and Possible Distances.

Paul S. Bonsma, Luis Cereceda, Jan van den Heuvel, Matthew Johnson

Electron. Notes Discret. Math., 2007

2006

Cycle decompositions of the complete graph.

Anthony J. W. Hilton, Matthew Johnson

Ars Comb., 2006

2004

Characterization of graphs with hall number 2.

Changiz Eslahchi, Matthew Johnson

J. Graph Theory, 2004

Amalgamations of factorizations of complete equipartite graphs.

Anthony J. W. Hilton, Matthew Johnson

Discret. Math., 2004

The External Network Problem with Edge- or Arc-Connectivity Requirements.

Jan van den Heuvel, Matthew Johnson

Proceedings of the Combinatorial and Algorithmic Aspects of Networking, 2004

2003

An algorithm for finding factorizations of complete graphs.

Anthony J. W. Hilton, Matthew Johnson

J. Graph Theory, 2003

Amalgamations of connected k-factorizations.

Anthony J. W. Hilton, Matthew Johnson, Christopher A. Rodger, Evan B. Wantland

J. Comb. Theory B, 2003

Defining sets for Latin squares given that they are based on groups.

David Bedford, Matthew Johnson, Matthew A. Ollis

Eur. J. Comb., 2003

2001

Weak critical sets in cyclic Latin squares.

Matthew Johnson, David Bedford

Australas. J Comb., 2001