Barnaby Martin

175 papers A* 11A 10B 15C 14Misc 6Journal 113Unranked 4
YearRankTypeTitle / Venue / Authors
2026 B conf
Quantified Colouring and H-Free Algorithmics.
SOFSEM
Kristina Asimi, Tala Eagling-Vose, Santiago Guzmán-Pro, Barnaby Martin, Yiming Qiu
2026 J jnl
Steiner Forest for
CoRR
Tala Eagling-Vose, David C. Kutner, Felicia Lucke, Dániel Marx, Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
2025 J jnl
A forbidden subgraph study for cut problems on graphs permitting loops and multiedges.
CoRR
Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Siani Smith
2025 J jnl
Acyclic, star and injective colouring: A complexity picture for H-free graphs.
J. Comput. Syst. Sci.
Jan Bok, Nikola Jedlicková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, Siani Smith
2025 J jnl
Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification.
CoRR
Tala Eagling-Vose, Jorik Jooken, Felicia Lucke, Barnaby Martin, Daniël Paulusma
2025 J jnl
Complexity Framework for Forbidden Subgraphs I: The Framework.
Algorithmica
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2025 J jnl
Complexity framework for forbidden subgraphs IV: The Steiner Forest problem.
J. Comput. Syst. Sci.
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2025 A* conf
Restricted CSPs and F-Free Digraph Algorithmics.
ICALP
Santiago Guzmán-Pro, Barnaby Martin
2025 J jnl
Restricted CSPs and F-free Digraph Algorithmics.
CoRR
Santiago Guzmán-Pro, Barnaby Martin
2024 J jnl
Complexity Classification Transfer for CSPs via Algebraic Products.
SIAM J. Comput.
Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová
2024 B conf
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs.
ISAAC
Vadim V. Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark H. Siggers, Siani Smith, Erik Jan van Leeuwen
2024 C conf
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.
IWOCA
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2024 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
Log. Methods Comput. Sci.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2024 — conf
Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs.
SWAT
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2024 C conf
Graph Homomorphism, Monotone Classes and Bounded Pathwidth.
CiE
Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Siani Smith
2024 J jnl
Graph Homomorphism, Monotone Classes and Bounded Pathwidth.
CoRR
Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Mark H. Siggers, Siani Smith
2024 J jnl
Model-checking positive equality free logic on a fixed structure (direttissima).
CoRR
Manuel Bodirsky, Marcin Kozik, Florent R. Madelaine, Barnaby Martin, Michal Wrona
2024 J jnl
Proof Complexity and the Binary Encoding of Combinatorial Principles.
SIAM J. Comput.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2024 J jnl
The Riis Complexity Gap for QBF Resolution.
J. Satisf. Boolean Model. Comput.
Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
2023 B conf
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs.
MFCS
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2023 J jnl
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.
CoRR
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2023 J jnl
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.
CoRR
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2023 J jnl
Few induced disjoint paths for
Theor. Comput. Sci.
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2023 J jnl
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.
Algorithmica
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2023 J jnl
The Complexity of L(p, q)-Edge-Labelling.
Algorithmica
Gaétan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
2023 J jnl
The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation.
ACM Trans. Comput. Log.
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin, Dmitriy Zhuk
2023 A* conf
The complete classification for quantified equality constraints.
SODA
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
2022 J jnl
Acyclic, Star, and Injective Colouring: Bounding the Diameter.
Electron. J. Comb.
Christoph Brause, Petr A. Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma, Siani Smith
2022 J jnl
Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.
Theor. Comput. Sci.
Barnaby Martin, Daniël Paulusma, Siani Smith
2022 J jnl
Colouring graphs of bounded diameter in the absence of small cycles.
Discret. Appl. Math.
Barnaby Martin, Daniël Paulusma, Siani Smith
2022 J jnl
Complexity Classification Transfer for CSPs via Algebraic Products.
CoRR
Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová
2022 J jnl
Complexity Framework For Forbidden Subgraphs.
CoRR
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Complexity Framework for Forbidden Subgraphs: When Hardness Is Not Preserved under Edge Subdivision.
CoRR
Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 A conf
Depth Lower Bounds in Stabbing Planes for Combinatorial Principles.
STACS
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2022 J jnl
Disjoint paths and connected subgraphs for
Theor. Comput. Sci.
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs.
CoRR
Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniël Paulusma, Erik Jan van Leeuwen
2022 C conf
Few Induced Disjoint Paths for H-Free Graphs.
ISCO
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Few Induced Disjoint Paths for H-Free Graphs.
CoRR
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Hard problems that quickly become very easy.
Inf. Process. Lett.
Barnaby Martin, Daniël Paulusma, Siani Smith
2022 B conf
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.
WG
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.
CoRR
Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2022 J jnl
Partitioning
Theor. Comput. Sci.
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
2022 J jnl
QCSP Monsters and the Demise of the Chen Conjecture.
J. ACM
Dmitriy Zhuk, Barnaby Martin
2022 J jnl
QCSP on Reflexive Tournaments.
ACM Trans. Comput. Log.
Benoît Larose, Barnaby Martin, Petar Markovic, Daniël Paulusma, Siani Smith, Stanislav Zivný
2022 B conf
The Complexity of L(p, q)-Edge-Labelling.
WALCOM
Gaétan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
2022 J jnl
The lattice and semigroup structure of multipermutations.
Int. J. Algebra Comput.
Catarina Carvalho, Barnaby Martin
2022 J jnl
When bounds consistency implies domain consistency for regular counting constraints.
Constraints An Int. J.
Barnaby Martin, Justin Pearson
2021 B conf
Acyclic, Star, and Injective Colouring: Bounding the Diameter.
WG
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
2021 J jnl
Acyclic, Star, and Injective Colouring: Bounding the Diameter.
CoRR
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
2021 J jnl
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter.
CoRR
Barnaby Martin, Daniël Paulusma, Siani Smith
2021 C conf
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles.
CIAC
Barnaby Martin, Daniël Paulusma, Siani Smith
2021 J jnl
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles.
CoRR
Barnaby Martin, Daniël Paulusma, Siani Smith
2021 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2021 J jnl
Depth lower bounds in Stabbing Planes for combinatorial principles.
Electron. Colloquium Comput. Complex.
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2021 C conf
Disjoint Paths and Connected Subgraphs for H-Free Graphs.
IWOCA
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2021 J jnl
Disjoint Paths and Connected Subgraphs for H-Free Graphs.
CoRR
Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
2021 Misc conf
Injective Colouring for H-Free Graphs.
CSR
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
2021 B conf
Partitioning H-Free Graphs of Bounded Diameter.
ISAAC
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
2021 J jnl
Partitioning H-Free Graphs of Bounded Diameter.
CoRR
Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma, Siani Smith
2021 A conf
QCSP on Reflexive Tournaments.
ESA
Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný
2021 J jnl
QCSP on Reflexive Tournaments.
CoRR
Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, Stanislav Zivný
2021 J jnl
The complete classification for quantified equality constraints.
CoRR
Dmitriy Zhuk, Barnaby Martin
2021 J jnl
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation.
CoRR
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin, Dmitriy Zhuk
2020 A conf
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs.
ESA
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
2020 J jnl
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs.
CoRR
Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith
2020 J jnl
Disconnected cuts in claw-free graphs.
J. Comput. Syst. Sci.
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
2020 J jnl
Hard Problems That Quickly Become Very Easy.
CoRR
Barnaby Martin, Daniël Paulusma, Siani Smith
2020 J jnl
Proof complexity and the binary encoding of combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
2020 A* conf
QCSP monsters and the demise of the chen conjecture.
STOC
Dmitriy Zhuk, Barnaby Martin
2020 B conf
Sherali-Adams and the Binary Encoding of Combinatorial Principles.
LATIN
Stefan S. Dantchev, Abdul Ghani, Barnaby Martin
2020 J jnl
The complexity of L(p, q)-Edge-Labelling.
CoRR
Gaétan Berthe, Barnaby Martin, Daniël Paulusma, Siani Smith
2019 B conf
Colouring H-Free Graphs of Bounded Diameter.
MFCS
Barnaby Martin, Daniël Paulusma, Siani Smith
2019 C ed.
Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019, Proceedings
CiE
Florin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero
2019 J jnl
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.
SIAM J. Comput.
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
2019 J jnl
QCSP monsters and the demise of the Chen Conjecture.
CoRR
Dmitriy Zhuk, Barnaby Martin
2019 J jnl
Report on BCTCS & AlgoUK 2019.
Bull. EATCS
Matthew Johnson, Barnaby Martin, George B. Mertzios, Daniël Paulusma
2019 A conf
Resolution and the Binary Encoding of Combinatorial Principles.
CCC
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2019 J jnl
Sherali-Adams and the binary encoding of combinatorial principles.
CoRR
Stefan S. Dantchev, Abdul Ghani, Barnaby Martin
2019 J jnl
Surjective H-Colouring over Reflexive Digraphs.
ACM Trans. Comput. Theory
Benoît Larose, Barnaby Martin, Daniël Paulusma
2019 J jnl
Surjective H-colouring: New hardness results.
Comput.
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
2018 A* conf
Classification Transfer for Qualitative Reasoning Problems.
IJCAI
Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet
2018 J jnl
Classification transfer for qualitative reasoning problems.
CoRR
Barnaby Martin, Peter Jonsson, Manuel Bodirsky, Antoine Mottet
2018 B conf
Consistency for Counting Quantifiers.
MFCS
Florent R. Madelaine, Barnaby Martin
2018 A conf
Disconnected Cuts in Claw-free Graphs.
ESA
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
2018 J jnl
Disconnected Cuts in Claw-free Graphs.
CoRR
Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen
2018 J jnl
Discrete Temporal Constraint Satisfaction Problems.
J. ACM
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
2018 J jnl
On the Complexity of the Model Checking Problem.
SIAM J. Comput.
Florent R. Madelaine, Barnaby Martin
2018 J jnl
Resolution and the binary encoding of combinatorial principles.
CoRR
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2018 J jnl
Resolution and the binary encoding of combinatorial principles.
Electron. Colloquium Comput. Complex.
Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
2018 A conf
Surjective H-Colouring over Reflexive Digraphs.
STACS
Benoît Larose, Barnaby Martin, Daniël Paulusma
2018 B conf
The Complexity of Disjunctive Linear Diophantine Constraints.
MFCS
Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet
2018 J jnl
The Riis Complexity Gap for QBF Resolution.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
2018 J jnl
The complexity of disjunctive linear Diophantine constraints.
CoRR
Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet
2017 J jnl
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic.
Theor. Comput. Sci.
Christian Glaßer, Peter Jonsson, Barnaby Martin
2017 J jnl
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs.
ACM Trans. Comput. Log.
Petar Dapic, Petar Markovic, Barnaby Martin
2017 — ch.
Quantified Constraints in Twenty Seventeen.
The Constraint Satisfaction Problem
Barnaby Martin
2017 J jnl
Surjective H-Colouring over Reflexive Digraphs.
CoRR
Benoît Larose, Barnaby Martin, Daniël Paulusma
2017 C conf
Surjective H-Colouring: New Hardness Results.
CiE
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
2017 J jnl
Surjective H-Colouring: New Hardness Results.
CoRR
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart
2017 B conf
The Complexity of Quantified Constraints Using the Algebraic Formulation.
MFCS
Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk
2017 J jnl
The complexity of counting quantifiers on equality languages.
Theor. Comput. Sci.
Barnaby Martin, András Pongrácz, Michal Wrona
2017 J jnl
The complexity of quantified constraints.
CoRR
Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk
2017 J jnl
The packing chromatic number of the infinite square lattice is between 13 and 15.
Discret. Appl. Math.
Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin
2016 C conf
Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic.
CiE
Christian Glaßer, Peter Jonsson, Barnaby Martin
2016 A* conf
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.
ICALP
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
2016 J jnl
Constraint satisfaction problems for reducts of homogeneous graphs.
CoRR
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz
2016 J jnl
Distance constraint satisfaction problems.
Inf. Comput.
Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Antoine Mottet, Michael Pinsker
2016 J jnl
On the Chen Conjecture regarding the complexity of QCSPs.
CoRR
Barnaby Martin
2016 J jnl
Report on BCTCS 2015.
Bull. EATCS
Barnaby Martin
2016 C conf
The Complexity of Counting Quantifiers on Equality Languages.
CiE
Barnaby Martin, András Pongrácz, Michal Wrona
2015 J jnl
Constraint Satisfaction Problems around Skolem Arithmetic.
CoRR
Christian Glaßer, Peter Jonsson, Barnaby Martin
2015 — conf
Constraint Satisfaction Problems over the Integers with Successor.
ICALP (1)
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
2015 J jnl
Constraint Satisfaction with Counting Quantifiers.
SIAM J. Discret. Math.
Barnaby Martin, Florent R. Madelaine, Juraj Stacho
2015 J jnl
Discrete Temporal Constraint Satisfaction Problems.
CoRR
Manuel Bodirsky, Barnaby Martin, Antoine Mottet
2015 B conf
First-Order Queries on Finite Abelian Groups.
CSL
Simone Bova, Barnaby Martin
2015 A* conf
From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP.
LICS
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin
2015 J jnl
From complexity to algebra and back: digraph classes, collapsibility and the PGP.
CoRR
Catarina Carvalho, Florent R. Madelaine, Barnaby Martin
2015 J jnl
Quantified Constraints and Containment Problems.
Log. Methods Comput. Sci.
Hubie Chen, Florent R. Madelaine, Barnaby Martin
2015 J jnl
Switchability and collapsibility of Gap Algebras.
CoRR
Barnaby Martin, Dmitriy Zhuk
2015 J jnl
The computational complexity of disconnected cut and 2
J. Comb. Theory B
Barnaby Martin, Daniël Paulusma
2015 J jnl
The packing chromatic number of the infinite square lattice is less than or equal to 16.
CoRR
Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin
2014 Misc conf
Constraint Satisfaction with Counting Quantifiers 2.
CSR
Barnaby Martin, Juraj Stacho
2014 — conf
QCSP on Semicomplete Digraphs.
ICALP (1)
Petar Dapic, Petar Markovic, Barnaby Martin
2014 J jnl
Relativization makes contradictions harder for Resolution.
Ann. Pure Appl. Log.
Stefan S. Dantchev, Barnaby Martin
2013 J jnl
Constraint Satisfaction with Counting Quantifiers 2.
CoRR
Barnaby Martin, Juraj Stacho
2013 Misc conf
Parameterized Resolution with Bounded Conjunction.
CSR
Stefan S. Dantchev, Barnaby Martin
2013 Misc conf
QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability.
CSR
Florent R. Madelaine, Barnaby Martin
2013 J jnl
QCSP on partially reflexive cycles - the wavy line of tractability
CoRR
Florent R. Madelaine, Barnaby Martin
2013 J jnl
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems.
Comput. Complex.
Stefan S. Dantchev, Barnaby Martin
2013 J jnl
Relativisation makes contradictions harder for Resolution
CoRR
Stefan S. Dantchev, Barnaby Martin
2012 Misc conf
Constraint Satisfaction with Counting Quantifiers.
CSR
Florent R. Madelaine, Barnaby Martin, Juraj Stacho
2012 A conf
Containment, Equivalence and Coreness from CSP to QCSP and Beyond.
CP
Florent R. Madelaine, Barnaby Martin
2012 J jnl
Containment, Equivalence and Coreness from CSP to QCSP and beyond
CoRR
Florent R. Madelaine, Barnaby Martin
2012 J jnl
Cutting Planes and the Parameter Cutwidth.
Theory Comput. Syst.
Stefan S. Dantchev, Barnaby Martin
2012 Misc conf
Finding Vertex-Surjective Graph Homomorphisms.
CSR
Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma
2012 J jnl
Finding vertex-surjective graph homomorphisms
CoRR
Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma
2012 J jnl
Finding vertex-surjective graph homomorphisms.
Acta Informatica
Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma
2012 J jnl
On the complexity of the model checking problem
CoRR
Florent R. Madelaine, Barnaby Martin
2012 J jnl
Parameterized Proof Complexity and W[1]
CoRR
Barnaby Martin
2012 J jnl
Parameterized Resolution with bounded conjunction
CoRR
Stefan S. Dantchev, Barnaby Martin
2012 J jnl
The Complexity of Positive First-Order Logic without Equality.
ACM Trans. Comput. Log.
Florent R. Madelaine, Barnaby Martin
2012 J jnl
The complexity of surjective homomorphism problems - a survey.
Discret. Appl. Math.
Manuel Bodirsky, Jan Kára, Barnaby Martin
2012 J jnl
The limits of tractability in Resolution-based propositional proof systems.
Ann. Pure Appl. Log.
Stefan S. Dantchev, Barnaby Martin
2011 A* conf
A Tetrachotomy for Positive First-Order Logic without Equality.
LICS
Florent R. Madelaine, Barnaby Martin
2011 J jnl
Constraint Satisfaction with Counting Quantifiers
CoRR
Florent R. Madelaine, Barnaby Martin, Juraj Stacho
2011 J jnl
Low-level dichotomy for Quantified Constraint Satisfaction Problems
CoRR
Barnaby Martin
2011 J jnl
Low-level dichotomy for quantified constraint satisfaction problems.
Inf. Process. Lett.
Barnaby Martin
2011 J jnl
Parameterized Proof Complexity.
Comput. Complex.
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider
2011 A conf
QCSP on Partially Reflexive Forests.
CP
Barnaby Martin
2011 J jnl
QCSP on partially reflexive forests
CoRR
Barnaby Martin
2011 J jnl
The Complexity of Surjective Homomorphism Problems -- a Survey
CoRR
Manuel Bodirsky, Jan Kára, Barnaby Martin
2011 A conf
The Computational Complexity of Disconnected Cut and 2K 2-Partition.
CP
Barnaby Martin, Daniël Paulusma
2011 J jnl
The Computational Complexity of Disconnected Cut and 2K2-Partition
CoRR
Barnaby Martin, Daniël Paulusma
2010 J jnl
Distance Constraint Satisfaction Problems
CoRR
Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker
2010 B conf
Distance Constraint Satisfaction Problems.
MFCS
Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker
2010 A* conf
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction.
LICS
Manuel Bodirsky, Martin Hils, Barnaby Martin
2010 B conf
The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case.
CSL
Barnaby Martin, Jos Martin
2010 A conf
The Lattice Structure of Sets of Surjective Hyper-Operations.
CP
Barnaby Martin
2010 C conf
The Limits of Tractability in Resolution-Based Propositional Proof Systems.
CiE
Stefan S. Dantchev, Barnaby Martin
2010 J jnl
The complexity of positive first-order logic without equality
CoRR
Florent R. Madelaine, Barnaby Martin
2009 C conf
Cutting Planes and the Parameter Cutwidth.
CiE
Stefan S. Dantchev, Barnaby Martin
2009 J jnl
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
Log. Methods Comput. Sci.
Manuel Bodirsky, Martin Hils, Barnaby Martin
2009 A* conf
The Complexity of Positive First-order Logic without Equality.
LICS
Florent R. Madelaine, Barnaby Martin
2009 — conf
The complexity of positive first-order logic without equality II: The four-element case.
The Constraint Satisfaction Problem: Complexity and Approximability
Barnaby Martin, Jos Martin
2009 J jnl
Tight rank lower bounds for the Sherali-Adams proof system.
Theor. Comput. Sci.
Stefan S. Dantchev, Barnaby Martin, Mark Nicholas Charles Rhodes
2008 C conf
First-Order Model Checking Problems Parameterized by the Model.
CiE
Barnaby Martin
2008 J jnl
Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three
CoRR
Barnaby Martin
2008 A* conf
Quantified Constraints and Containment Problems.
LICS
Hubie Chen, Florent R. Madelaine, Barnaby Martin
2007 C conf
Hierarchies in Fragments of Monadic Strict NP.
CiE
Barnaby Martin, Florent R. Madelaine
2007 J jnl
On the Complexity of a Derivative Chess Problem
CoRR
Barnaby Martin
2007 A* conf
Parameterized Proof Complexity.
FOCS
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider
2007 J jnl
Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution.
Electron. Colloquium Comput. Complex.
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider
2006 J jnl
Dichotomies and Duality in First-order Model Checking Problems
CoRR
Barnaby Martin
2006 C conf
Towards a Trichotomy for Quantified
CiE
Barnaby Martin, Florent R. Madelaine
2005 — —
Logic, computation and constraint satisfaction.
Barnaby Martin