Barnaby Martin

ORCID

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 101

Top Venues

CoRR

Theor. Comput. Sci.

MFCS

Electron. Colloquium Comput. Complex.

University of Leicester, UK (PHD)

Education History

University of Leicester, UK

PHD

Publications

Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Depth lower bounds in Stabbing Planes for combinatorial principles. Log. Methods Comput. Sci. 20 (1) (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)
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
The complete classification for quantified equality constraints. SODA (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)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
-free graphs. Theor. Comput. Sci. 939 (2023)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica 85 (9) (2023)
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin, Dmitriy Zhuk
The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation. ACM Trans. Comput. Log. 24 (1) (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)
Gaétan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
The Complexity of L(p, q)-Edge-Labelling. Algorithmica 85 (11) (2023)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. WG (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. CoRR (2022)
Gaetan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
The Complexity of L(p, q)-Edge-Labelling. WALCOM (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)
Barnaby Martin, Justin Pearson
When bounds consistency implies domain consistency for regular counting constraints. Constraints An Int. J. 27 (3) (2022)
Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Complexity Framework for Forbidden Subgraphs: When Hardness Is Not Preserved under Edge Subdivision. CoRR (2022)
Dmitriy Zhuk, Barnaby Martin
QCSP Monsters and the Demise of the Chen Conjecture. J. ACM 69 (5) (2022)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma, Siani Smith
Acyclic, Star, and Injective Colouring: Bounding the Diameter. Electron. J. Comb. 29 (2) (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theor. Comput. Sci. 931 (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)
Benoît Larose, Barnaby Martin, Petar Markovic, Daniël Paulusma, Siani Smith, Stanislav Zivný
QCSP on Reflexive Tournaments. ACM Trans. Comput. Log. 23 (3) (2022)
Catarina Carvalho, Barnaby Martin
The lattice and semigroup structure of multipermutations. Int. J. Algebra Comput. 32 (2) (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith
Hard problems that quickly become very easy. Inf. Process. Lett. 174 (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Few Induced Disjoint Paths for H-Free Graphs. CoRR (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Few Induced Disjoint Paths for H-Free Graphs. ISCO (2022)
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Depth Lower Bounds in Stabbing Planes for Combinatorial Principles. STACS (2022)
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
-free graphs. Theor. Comput. Sci. 898 (2022)
Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová
Complexity Classification Transfer for CSPs via Algebraic Products. CoRR (2022)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
-free graphs of bounded diameter. Theor. Comput. Sci. 930 (2022)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring graphs of bounded diameter in the absence of small cycles. Discret. Appl. Math. 314 (2022)
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Disjoint Paths and Connected Subgraphs for H-Free Graphs. CoRR (2021)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. CIAC (2021)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
Acyclic, Star, and Injective Colouring: Bounding the Diameter. CoRR (2021)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. CoRR (2021)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter. CoRR (2021)
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
Injective Colouring for H-Free Graphs. CSR (2021)
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Disjoint Paths and Connected Subgraphs for H-Free Graphs. IWOCA (2021)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
Partitioning H-Free Graphs of Bounded Diameter. CoRR (2021)
Dmitriy Zhuk, Barnaby Martin
The complete classification for quantified equality constraints. CoRR (2021)
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Depth lower bounds in Stabbing Planes for combinatorial principles. CoRR (2021)
Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný
QCSP on Reflexive Tournaments. ESA (2021)
Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný
QCSP on Reflexive Tournaments. CoRR (2021)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
Partitioning H-Free Graphs of Bounded Diameter. ISAAC (2021)
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Depth lower bounds in Stabbing Planes for combinatorial principles. Electron. Colloquium Comput. Complex. 28 (2021)
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin, Dmitriy Zhuk
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. CoRR (2021)
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
Acyclic, Star, and Injective Colouring: Bounding the Diameter. WG (2021)
Barnaby Martin, Daniël Paulusma, Siani Smith
Hard Problems That Quickly Become Very Easy. CoRR (2020)
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. ESA (2020)
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Proof complexity and the binary encoding of combinatorial principles. CoRR (2020)
Dmitriy Zhuk, Barnaby Martin
QCSP monsters and the demise of the chen conjecture. STOC (2020)
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. CoRR (2020)
Gaetan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
The complexity of L(p, q)-Edge-Labelling. CoRR (2020)
Stefan S. Dantchev, Abdul Ghani, Barnaby Martin
Sherali-Adams and the Binary Encoding of Combinatorial Principles. LATIN (2020)
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
Disconnected cuts in claw-free graphs. J. Comput. Syst. Sci. 113 (2020)
Benoît Larose, Barnaby Martin, Daniël Paulusma
Surjective H-Colouring over Reflexive Digraphs. ACM Trans. Comput. Theory 11 (1) (2019)
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. SIAM J. Comput. 48 (4) (2019)
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
Resolution and the Binary Encoding of Combinatorial Principles. Computational Complexity Conference (2019)
Dmitriy Zhuk, Barnaby Martin
QCSP monsters and the demise of the Chen Conjecture. CoRR (2019)
Stefan S. Dantchev, Abdul Ghani, Barnaby Martin
Sherali-Adams and the binary encoding of combinatorial principles. CoRR (2019)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-colouring: New hardness results. Comput. 8 (1) (2019)
Matthew Johnson, Barnaby Martin, George B. Mertzios, Daniël Paulusma
Report on BCTCS & AlgoUK 2019. Bull. EATCS 128 (2019)
Barnaby Martin, Daniël Paulusma, Siani Smith
Colouring H-Free Graphs of Bounded Diameter. MFCS (2019)
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
Resolution and the binary encoding of combinatorial principles. CoRR (2018)
Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet
The complexity of disjunctive linear Diophantine constraints. CoRR (2018)
Barnaby Martin, Peter Jonsson, Manuel Bodirsky, Antoine Mottet
Classification transfer for qualitative reasoning problems. CoRR (2018)
Florent R. Madelaine, Barnaby Martin
On the Complexity of the Model Checking Problem. SIAM J. Comput. 47 (3) (2018)
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
Resolution and the binary encoding of combinatorial principles. Electron. Colloquium Comput. Complex. 25 (2018)
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
Disconnected Cuts in Claw-free Graphs. CoRR (2018)
Florent R. Madelaine, Barnaby Martin
Consistency for Counting Quantifiers. MFCS (2018)
Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet
Classification Transfer for Qualitative Reasoning Problems. IJCAI (2018)
Benoît Larose, Barnaby Martin, Daniël Paulusma
Surjective H-Colouring over Reflexive Digraphs. STACS (2018)
Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet
The Complexity of Disjunctive Linear Diophantine Constraints. MFCS (2018)
Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
The Riis Complexity Gap for QBF Resolution. Electron. Colloquium Comput. Complex. 25 (2018)
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
Discrete Temporal Constraint Satisfaction Problems. J. ACM 65 (2) (2018)
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
Disconnected Cuts in Claw-free Graphs. ESA (2018)
Christian Glaßer, Peter Jonsson, Barnaby Martin
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. Theor. Comput. Sci. 703 (2017)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-Colouring: New Hardness Results. CiE (2017)
Benoît Larose, Barnaby Martin, Daniël Paulusma
Surjective H-Colouring over Reflexive Digraphs. CoRR (2017)
Barnaby Martin, András Pongrácz, Michal Wrona
The complexity of counting quantifiers on equality languages. Theor. Comput. Sci. 670 (2017)
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
Surjective H-Colouring: New Hardness Results. CoRR (2017)
Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk
The complexity of quantified constraints. CoRR (2017)
Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin
The packing chromatic number of the infinite square lattice is between 13 and 15. Discret. Appl. Math. 225 (2017)
Petar Dapic, Petar Markovic, Barnaby Martin
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs. ACM Trans. Comput. Log. 18 (1) (2017)
Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk
The Complexity of Quantified Constraints Using the Algebraic Formulation. MFCS (2017)
Barnaby Martin
Report on BCTCS 2015. Bull. EATCS 118 (2016)
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
Constraint satisfaction problems for reducts of homogeneous graphs. CoRR (2016)
Barnaby Martin
On the Chen Conjecture regarding the complexity of QCSPs. CoRR (2016)
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. ICALP (2016)
Barnaby Martin, András Pongrácz, Michal Wrona
The Complexity of Counting Quantifiers on Equality Languages. CiE (2016)
Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Antoine Mottet, Michael Pinsker
Distance constraint satisfaction problems. Inf. Comput. 247 (2016)
Christian Glaßer, Peter Jonsson, Barnaby Martin
Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic. CiE (2016)
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin
From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. LICS (2015)
Barnaby Martin, Florent R. Madelaine, Juraj Stacho
Constraint Satisfaction with Counting Quantifiers. SIAM J. Discret. Math. 29 (2) (2015)
Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin
The packing chromatic number of the infinite square lattice is less than or equal to 16. CoRR (2015)
Barnaby Martin, Dmitriy Zhuk
Switchability and collapsibility of Gap Algebras. CoRR (2015)
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
Constraint Satisfaction Problems over the Integers with Successor. ICALP (1) (2015)
Barnaby Martin, Daniël Paulusma
-partition. J. Comb. Theory, Ser. B 111 (2015)
Christian Glaßer, Peter Jonsson, Barnaby Martin
Constraint Satisfaction Problems around Skolem Arithmetic. CoRR (2015)
Hubie Chen, Florent R. Madelaine, Barnaby Martin
Quantified Constraints and Containment Problems. Log. Methods Comput. Sci. 11 (3) (2015)
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin
From complexity to algebra and back: digraph classes, collapsibility and the PGP. CoRR (2015)
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
Discrete Temporal Constraint Satisfaction Problems. CoRR (2015)

Barnaby Martin.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Barnaby Martin