Matthew Johnson

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 67

Top Venues

Publications

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. SWAT (2024)
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Eur. J. Comb. 117 (2024)
Márton Benedek, Péter Biró, Gergely Csáji, Matthew Johnson, Daniël Paulusma, Xin Ye
Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded. AAMAS (2024)
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. IWOCA (2024)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. CoRR (2023)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. MFCS (2023)
Márton Benedek, Péter Biró, Gergely Csáji, Matthew Johnson, Daniël Paulusma, Xin Ye
Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded. CoRR (2023)
Márton Benedek, Péter Biró, Matthew Johnson, Daniël Paulusma, Xin Ye
The Complexity of Matching Games: A Survey. J. Artif. Intell. Res. 77 (2023)
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. CoRR (2023)
Nick Brettell, Matthew Johnson, Daniël Paulusma
-free graphs. J. Comput. Syst. Sci. 128 (2022)
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework For Forbidden Subgraphs. CoRR (2022)
Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma
-free graphs. Theor. Comput. Sci. 902 (2022)
Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs. CoRR (2022)
Márton Benedek, Péter Biró, Matthew Johnson, Daniël Paulusma, Xin Ye
The Complexity of Matching Games: A Survey. CoRR (2022)
Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen
Steiner trees for hereditary graph classes: A treewidth perspective. Theor. Comput. Sci. 867 (2021)
Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen
What Graphs are 2-Dot Product Graphs? Int. J. Comput. Geom. Appl. 31 (1) (2021)
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron
-Free Graphs: An Almost Complete Dichotomy. Algorithmica 83 (3) (2021)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration. J. Graph Theory 98 (1) (2021)
Nick Brettell, Matthew Johnson, Daniël Paulusma
Computing Weighted Subset Transversals in H-Free Graphs. WADS (2021)
Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, Daniël Paulusma
Preface. BCC (2021)
Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma
Computing Subset Transversals in H-Free Graphs. WG (2020)
Nick Brettell, Matthew Johnson, Daniël Paulusma
Computing Weighted Subset Transversals in H-Free Graphs. CoRR (2020)
Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. CoRR (2020)
Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Erik Jan van Leeuwen
Steiner Trees for Hereditary Graph Classes. LATIN (2020)
Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma
Computing Subset Transversals in H-Free Graphs. CoRR (2020)
Matthew Johnson, Giacomo Paesani, Daniël Paulusma
-Free Graphs. Algorithmica 82 (1) (2020)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, Viktor Zamaraev
Clique-Width for Graph Classes Closed under Complementation. SIAM J. Discret. Math. 34 (2) (2020)
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Pawel Rzazewski
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica 82 (10) (2020)
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, Stéphane Vialette
Finding a Small Number of Colourful Components. CPM (2019)
Marthe Bonamy, Nicolas Bousquet, Carl Feghali, Matthew Johnson
On a conjecture of Mohar concerning Kempe equivalence of regular graphs. J. Comb. Theory, Ser. B 135 (2019)
Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. FCT (2019)
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. CoRR (2019)
Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
)-Free Graphs: An Almost Complete Dichotomy. WADS (2019)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
-Free Graphs. Algorithmica 81 (4) (2019)
Konrad K. Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma
Filling the complexity gaps for colouring planar and bounded degree graphs. J. Graph Theory 92 (4) (2019)
Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
Clique-Width for Hereditary Graph Classes. CoRR (2019)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
Hereditary graph classes: When the complexities of coloring and clique cover coincide. J. Graph Theory 91 (3) (2019)
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Pawel Rzazewski
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. CoRR (2019)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-colouring: New hardness results. Comput. 8 (1) (2019)
Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
Clique-width for hereditary graph classes. BCC (2019)
Matthew Johnson, Barnaby Martin, George B. Mertzios, Daniël Paulusma
Report on BCTCS & AlgoUK 2019. Bull. EATCS 128 (2019)
Matthew Johnson, Giacomo Paesani, Daniël Paulusma
Connected Vertex Cover for (sP_1+P_5) ( s P 1 + P 5 ) -Free Graphs. WG (2018)
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, Stéphane Vialette
Finding a Small Number of Colourful Components. CoRR (2018)
Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
)-free Graphs: An Almost Complete Dichotomy. CoRR (2018)
Nina Chiarelli, Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma
Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theor. Comput. Sci. 705 (2018)
Carl Feghali, Matthew Johnson, Daniel Thomas
Erdős-Ko-Rado theorems for a family of trees. Discret. Appl. Math. 236 (2018)
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. MFCS (2018)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Independent feedback vertex sets for graphs of bounded diameter. Inf. Process. Lett. 131 (2018)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Independent Feedback Vertex Set for P_5-free Graphs. ISAAC (2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. CoRR (2017)
Nina Chiarelli, Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma
Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity. CoRR (2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Recognizing Graphs Close to Bipartite Graphs. MFCS (2017)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-Colouring: New Hardness Results. CiE (2017)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, Victor Zamaraev
Clique-Width for Graph Classes Closed under Complementation. CoRR (2017)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-Colouring: New Hardness Results. CoRR (2017)
Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song
A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. J. Graph Theory 84 (4) (2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Independent Feedback Vertex Sets for Graphs of Bounded Diameter. CoRR (2017)
Carl Feghali, Matthew Johnson, Daniël Paulusma
Kempe equivalence of colourings of cubic graphs. Eur. J. Comb. 59 (2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma
Independent Feedback Vertex Set for $P_5$-free Graphs. CoRR (2017)
Matthew Johnson, Giacomo Paesani, Daniël Paulusma
)-Free Graphs. CoRR (2017)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, Viktor Zamaraev
Clique-Width for Graph Classes Closed under Complementation. MFCS (2017)
Foad Lotfifar, Matthew Johnson
A Serial Multilevel Hypergraph Partitioning Algorithm. CoRR (2016)
Markus Mäsker, Lars Nagel, André Brinkmann, Foad Lotfifar, Matthew Johnson
Smart Grid-aware scheduling in data centres. Comput. Commun. 96 (2016)
Alexandre Blanché, Konrad Kazimierz Dabrowski, Matthew Johnson, Daniël Paulusma
Colouring on Hereditary Graph Classes Closed under Complementation. CoRR (2016)
Carl Feghali, Matthew Johnson, Daniël Paulusma
A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. J. Graph Theory 83 (4) (2016)
Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma
The price of connectivity for cycle transversals. Eur. J. Comb. 58 (2016)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Finding Shortest Paths Between Graph Colourings. Algorithmica 75 (2) (2016)
Konrad Kazimierz Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs. IWOCA (2015)
Carl Feghali, Matthew Johnson, Daniël Paulusma
Kempe Equivalence of Colourings of Cubic Graphs. Electron. Notes Discret. Math. 49 (2015)
Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen
Algorithms for diversity and clustering in social networks through dot product graphs. Soc. Networks 41 (2015)
Matthew Johnson, Erik Jan van Leeuwen, Daniël Paulusma
What Graphs are 2-Dot Product Graphs? Electron. Notes Discret. Math. 49 (2015)
Carl Feghali, Matthew Johnson, Daniël Paulusma
A Reconfigurations Analogue of Brooks' Theorem and its Consequences. CoRR (2015)
Foad Lotfifar, Matthew Johnson
A Multi-level Hypergraph Partitioning Algorithm Using Rough Set Clustering. Euro-Par (2015)
Shenwei Huang, Matthew Johnson, Daniël Paulusma
)-Free Graphs. Comput. J. 58 (11) (2015)
Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen
What Graphs are 2-Dot Product Graphs? CoRR (2015)
Marthe Bonamy, Nicolas Bousquet, Carl Feghali, Matthew Johnson
On a conjecture of Mohar concerning Kempe equivalence of regular graphs. CoRR (2015)
Matthew Johnson, Daniël Paulusma, Anthony Stewart
-free graphs. Discret. Appl. Math. (2015)
Carl Feghali, Matthew Johnson, Daniël Paulusma
Kempe Equivalence of Colourings of Cubic Graphs. CoRR (2015)
Konrad Kazimierz Dabrowski, François Dross, Matthew Johnson, Daniël Paulusma
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs. CoRR (2015)
Markus Mäsker, Lars Nagel, André Brinkmann, Foad Lotfifar, Matthew Johnson
Smart grid-aware scheduling in data centres. SustainIT (2015)
Tatiana Romina Hartinger, Matthew Johnson, Martin Milanic, Daniël Paulusma
The Price of Connectivity for Cycle Transversals. MFCS (2) (2015)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Colouring Reconfiguration Is Fixed-Parameter Tractable. CoRR (2014)
Matthew Johnson, Daniël Paulusma, Anthony Stewart
Knocking Out P k -free Graphs. MFCS (2) (2014)
Shenwei Huang, Matthew Johnson, Daniël Paulusma
Narrowing the Complexity Gap for Colouring ($C_s$, $P_t$)-Free Graphs. CoRR (2014)
Shenwei Huang, Matthew Johnson, Daniël Paulusma
Narrowing the Complexity Gap for Colouring (C s , P t )-Free Graphs. AAIM (2014)
Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, Daniël Paulusma
Finding Shortest Paths Between Graph Colourings. IPEC (2014)
Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs. CoRR (2014)
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Comb. Optim. 27 (1) (2014)
Matthew Johnson, Viresh Patel, Daniël Paulusma, Théophile Trunck
Obtaining Online Ecological Colourings by Generalizing First-Fit. Theory Comput. Syst. 54 (2) (2014)
Carl Feghali, Matthew Johnson, Daniël Paulusma
A Reconfigurations Analogue of Brooks' Theorem. MFCS (2) (2014)
Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen
Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. ISAAC (2013)
Iain A. Stewart, Daniël Paulusma, Matthew Johnson
Editorial. J. Discrete Algorithms 12 (2012)
Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma
On the diameter of reconfiguration graphs for vertex colourings. Electron. Notes Discret. Math. 38 (2011)
Luis Cereceda, Jan van den Heuvel, Matthew Johnson
Finding paths between 3-colorings. J. Graph Theory 67 (1) (2011)
Matthew Johnson, Viresh Patel, Daniël Paulusma, Théophile Trunck
Obtaining Online Ecological Colourings by Generalizing First-Fit. CSR (2010)
Hajo Broersma, Stefan S. Dantchev, Matthew Johnson, Stefan Szeider
Editorial. J. Discrete Algorithms 8 (2) (2010)
Matthew Johnson, Daniël Paulusma, Chantal Wood
Path factors and parallel knock-out schemes of almost claw-free graphs. Discret. Math. 310 (9) (2010)
Hajo Broersma, Stefan S. Dantchev, Matthew Johnson, Stefan Szeider
Editorial. J. Discrete Algorithms 7 (2) (2009)
Luis Cereceda, Jan van den Heuvel, Matthew Johnson
Mixing 3-colourings in bipartite graphs. Eur. J. Comb. 30 (7) (2009)
Hajo Broersma, Matthew Johnson, Daniël Paulusma
Upper bounds and algorithms for parallel knock-out numbers. Theor. Comput. Sci. 410 (14) (2009)

Matthew Johnson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Matthew Johnson