default search action
Barnaby Martin
Person information
- affiliation: Durham University, UK
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2005
- [b1]Barnaby Martin
:
Logic, computation and constraint satisfaction. University of Leicester, UK, 2005
Journal Articles
- 2024
- [j45]Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin:
The Riis Complexity Gap for QBF Resolution. J. Satisf. Boolean Model. Comput. 15(1): 9-25 (2024) - [j44]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) - [j43]Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Proof Complexity and the Binary Encoding of Combinatorial Principles. SIAM J. Comput. 53(3): 764-802 (2024) - [j42]Manuel Bodirsky
Complexity Classification Transfer for CSPs via Algebraic Products. SIAM J. Comput. 53(5): 1293-1353 (2024) - 2023
- [j41]Barnaby Martin
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica 85(9): 2580-2604 (2023) - [j40]Gaétan Berthe
The Complexity of L(p, q)-Edge-Labelling. Algorithmica 85(11): 3406-3429 (2023) - [j39]Barnaby Martin, Daniël Paulusma
Few induced disjoint paths for H-free graphs. Theor. Comput. Sci. 939: 182-193 (2023) - [j38]Catarina Carvalho
The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation. ACM Trans. Comput. Log. 24(1): 5:1-5:26 (2023) - 2022
- [j37]Christoph Brause, Petr A. Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma
Acyclic, Star, and Injective Colouring: Bounding the Diameter. Electron. J. Comb. 29(2) (2022) - [j36]Barnaby Martin, Justin Pearson
When bounds consistency implies domain consistency for regular counting constraints. Constraints An Int. J. 27(3): 161-167 (2022) - [j35]Barnaby Martin, Daniël Paulusma
Colouring graphs of bounded diameter in the absence of small cycles. Discret. Appl. Math. 314: 150-161 (2022) - [j34]Catarina Carvalho
The lattice and semigroup structure of multipermutations. Int. J. Algebra Comput. 32(2): 211-235 (2022) - [j33]Barnaby Martin, Daniël Paulusma
Hard problems that quickly become very easy. Inf. Process. Lett. 174: 106213 (2022) - [j32]Dmitriy Zhuk
QCSP Monsters and the Demise of the Chen Conjecture. J. ACM 69(5): 35:1-35:44 (2022) - [j31]Walter Kern, Barnaby Martin, Daniël Paulusma
Disjoint paths and connected subgraphs for H-free graphs. Theor. Comput. Sci. 898: 59-68 (2022) - [j30]Christoph Brause, Petr A. Golovach
Partitioning H-free graphs of bounded diameter. Theor. Comput. Sci. 930: 37-52 (2022) - [j29]Barnaby Martin, Daniël Paulusma
Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theor. Comput. Sci. 931: 104-116 (2022) - [j28]Benoît Larose, Barnaby Martin
QCSP on Reflexive Tournaments. ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022) - 2020
- [j27]Barnaby Martin, Daniël Paulusma
Disconnected cuts in claw-free graphs. J. Comput. Syst. Sci. 113: 60-75 (2020) - 2019
- [j26]Petr A. Golovach, Matthew Johnson, Barnaby Martin
Surjective H-colouring: New hardness results. Comput. 8(1): 27-42 (2019) - [j25]Matthew Johnson, Barnaby Martin
Report on BCTCS & AlgoUK 2019. Bull. EATCS 128 (2019) - [j24]Manuel Bodirsky
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. SIAM J. Comput. 48(4): 1224-1264 (2019) - [j23]Benoît Larose, Barnaby Martin
Surjective H-Colouring over Reflexive Digraphs. ACM Trans. Comput. Theory 11(1): 3:1-3:21 (2019) - 2018
- [j22]Manuel Bodirsky
Discrete Temporal Constraint Satisfaction Problems. J. ACM 65(2): 9:1-9:41 (2018) - [j21]Florent R. Madelaine
On the Complexity of the Model Checking Problem. SIAM J. Comput. 47(3): 769-797 (2018) - 2017
- [j20]Barnaby Martin
The packing chromatic number of the infinite square lattice is between 13 and 15. Discret. Appl. Math. 225: 136-142 (2017) - [j19]Barnaby Martin
The complexity of counting quantifiers on equality languages. Theor. Comput. Sci. 670: 56-67 (2017) - [j18]Christian Glaßer, Peter Jonsson, Barnaby Martin
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. Theor. Comput. Sci. 703: 18-36 (2017) - [j17]Petar Dapic
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs. ACM Trans. Comput. Log. 18(1): 2:1-2:47 (2017) - 2016
- [j16]Barnaby Martin
Report on BCTCS 2015. Bull. EATCS 118 (2016) - [j15]Manuel Bodirsky
Distance constraint satisfaction problems. Inf. Comput. 247: 87-105 (2016) - 2015
- [j14]Hubie Chen, Florent R. Madelaine
Quantified Constraints and Containment Problems. Log. Methods Comput. Sci. 11(3) (2015) - [j13]Barnaby Martin
The computational complexity of disconnected cut and 2K2-partition. J. Comb. Theory B 111: 17-37 (2015) - [j12]Barnaby Martin
Constraint Satisfaction with Counting Quantifiers. SIAM J. Discret. Math. 29(2): 1065-1113 (2015) - 2014
- [j11]Stefan S. Dantchev
Relativization makes contradictions harder for Resolution. Ann. Pure Appl. Log. 165(3): 837-857 (2014) - 2013
- [j10]Stefan S. Dantchev
Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Comput. Complex. 22(1): 191-213 (2013) - 2012
- [j9]Petr A. Golovach
Finding vertex-surjective graph homomorphisms. Acta Informatica 49(6): 381-394 (2012) - [j8]Stefan S. Dantchev
The limits of tractability in Resolution-based propositional proof systems. Ann. Pure Appl. Log. 163(6): 656-668 (2012) - [j7]Manuel Bodirsky
The complexity of surjective homomorphism problems - a survey. Discret. Appl. Math. 160(12): 1680-1690 (2012) - [j6]Stefan S. Dantchev, Barnaby Martin
Cutting Planes and the Parameter Cutwidth. Theory Comput. Syst. 51(1): 50-64 (2012) - [j5]Florent R. Madelaine
The Complexity of Positive First-Order Logic without Equality. ACM Trans. Comput. Log. 13(1): 5:1-5:17 (2012) - 2011
- [j4]Stefan S. Dantchev
Parameterized Proof Complexity. Comput. Complex. 20(1): 51-85 (2011) - [j3]Barnaby Martin
Low-level dichotomy for quantified constraint satisfaction problems. Inf. Process. Lett. 111(20): 999-1003 (2011) - 2009
- [j2]Manuel Bodirsky, Martin Hils
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction. Log. Methods Comput. Sci. 8(3) (2009) - [j1]Stefan S. Dantchev, Barnaby Martin
Tight rank lower bounds for the Sherali-Adams proof system. Theor. Comput. Sci. 410(21-23): 2054-2063 (2009)
Conference and Workshop Papers
- 2024
- [c56]Tala Eagling-Vose
Graph Homomorphism, Monotone Classes and Bounded Pathwidth. CiE 2024: 233-251 - [c55]Vadim V. Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark H. Siggers, Siani Smith, Erik Jan van Leeuwen:
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. ISAAC 2024: 47:1-47:18 - [c54]Hans L. Bodlaender
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. IWOCA 2024: 206-217 - [c53]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: 29:1-29:17 - 2023
- [c52]Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. MFCS 2023: 57:1-57:15 - [c51]Dmitriy Zhuk, Barnaby Martin, Michal Wrona:
The complete classification for quantified equality constraints. SODA 2023: 2746-2760 - 2022
- [c50]Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen:
Few Induced Disjoint Paths for H-Free Graphs. ISCO 2022: 89-101 - [c49]Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Depth Lower Bounds in Stabbing Planes for Combinatorial Principles. STACS 2022: 24:1-24:18 - [c48]Gaétan Berthe
The Complexity of L(p, q)-Edge-Labelling. WALCOM 2022: 175-186 - [c47]Barnaby Martin
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. WG 2022: 398-411 - 2021
- [c46]Barnaby Martin, Daniël Paulusma
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. CIAC 2021: 367-380 - [c45]Jan Bok
Injective Colouring for H-Free Graphs. CSR 2021: 18-30 - [c44]Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma
QCSP on Reflexive Tournaments. ESA 2021: 58:1-58:15 - [c43]Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma
Partitioning H-Free Graphs of Bounded Diameter. ISAAC 2021: 21:1-21:14 - [c42]Walter Kern, Barnaby Martin, Daniël Paulusma
Disjoint Paths and Connected Subgraphs for H-Free Graphs. IWOCA 2021: 414-427 - [c41]Christoph Brause, Petr A. Golovach
Acyclic, Star, and Injective Colouring: Bounding the Diameter. WG 2021: 336-348 - 2020
- [c40]Jan Bok
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. ESA 2020: 22:1-22:22 - [c39]Stefan S. Dantchev, Abdul Ghani, Barnaby Martin:
Sherali-Adams and the Binary Encoding of Combinatorial Principles. LATIN 2020: 336-347 - [c38]Dmitriy Zhuk, Barnaby Martin
QCSP monsters and the demise of the chen conjecture. STOC 2020: 91-104 - 2019
- [c37]Stefan S. Dantchev
Resolution and the Binary Encoding of Combinatorial Principles. CCC 2019: 6:1-6:25 - [c36]Barnaby Martin
Colouring H-Free Graphs of Bounded Diameter. MFCS 2019: 14:1-14:14 - 2018
- [c35]Barnaby Martin
Disconnected Cuts in Claw-free Graphs. ESA 2018: 61:1-61:14 - [c34]Manuel Bodirsky
Classification Transfer for Qualitative Reasoning Problems. IJCAI 2018: 1256-1262 - [c33]Florent R. Madelaine
Consistency for Counting Quantifiers. MFCS 2018: 11:1-11:13 - [c32]Manuel Bodirsky
The Complexity of Disjunctive Linear Diophantine Constraints. MFCS 2018: 33:1-33:16 - [c31]Benoît Larose, Barnaby Martin
Surjective H-Colouring over Reflexive Digraphs. STACS 2018: 49:1-49:14 - 2017
- [c30]Petr A. Golovach
Surjective H-Colouring: New Hardness Results. CiE 2017: 270-281 - [c29]Catarina Carvalho
The Complexity of Quantified Constraints Using the Algebraic Formulation. MFCS 2017: 27:1-27:14 - 2016
- [c28]Christian Glaßer, Peter Jonsson, Barnaby Martin:
Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic. CiE 2016: 323-332 - [c27]Barnaby Martin, András Pongrácz, Michal Wrona:
The Complexity of Counting Quantifiers on Equality Languages. CiE 2016: 333-342 - [c26]Manuel Bodirsky, Barnaby Martin
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. ICALP 2016: 119:1-119:14 - 2015
- [c25]Simone Bova, Barnaby Martin
First-Order Queries on Finite Abelian Groups. CSL 2015: 41-59 - [c24]Manuel Bodirsky
Constraint Satisfaction Problems over the Integers with Successor. ICALP (1) 2015: 256-267 - [c23]Catarina Carvalho
From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. LICS 2015: 462-474 - 2014
- [c22]Barnaby Martin, Juraj Stacho:
Constraint Satisfaction with Counting Quantifiers 2. CSR 2014: 259-272 - [c21]Petar Dapic
QCSP on Semicomplete Digraphs. ICALP (1) 2014: 847-858 - 2013
- [c20]Stefan S. Dantchev, Barnaby Martin:
Parameterized Resolution with Bounded Conjunction. CSR 2013: 139-149 - [c19]Florent R. Madelaine
QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability. CSR 2013: 322-333 - 2012
- [c18]Florent R. Madelaine
Containment, Equivalence and Coreness from CSP to QCSP and Beyond. CP 2012: 480-495 - [c17]Petr A. Golovach
Finding Vertex-Surjective Graph Homomorphisms. CSR 2012: 160-171 - [c16]Florent R. Madelaine
Constraint Satisfaction with Counting Quantifiers. CSR 2012: 253-265 - 2011
- [c15]Barnaby Martin:
QCSP on Partially Reflexive Forests. CP 2011: 546-560 - [c14]Barnaby Martin, Daniël Paulusma
The Computational Complexity of Disconnected Cut and 2K 2-Partition. CP 2011: 561-575 - [c13]Florent R. Madelaine
A Tetrachotomy for Positive First-Order Logic without Equality. LICS 2011: 311-320 - 2010
- [c12]Stefan S. Dantchev, Barnaby Martin:
The Limits of Tractability in Resolution-Based Propositional Proof Systems. CiE 2010: 98-107 - [c11]Barnaby Martin:
The Lattice Structure of Sets of Surjective Hyper-Operations. CP 2010: 368-382 - [c10]Barnaby Martin, Jos Martin:
The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case. CSL 2010: 426-438 - [c9]Manuel Bodirsky
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction. LICS 2010: 90-99 - [c8]Manuel Bodirsky
Distance Constraint Satisfaction Problems. MFCS 2010: 162-173 - 2009
- [c7]Stefan S. Dantchev, Barnaby Martin:
Cutting Planes and the Parameter Cutwidth. CiE 2009: 134-143 - [c6]Florent R. Madelaine
The Complexity of Positive First-order Logic without Equality. LICS 2009: 429-438 - 2008
- [c5]Barnaby Martin:
First-Order Model Checking Problems Parameterized by the Model. CiE 2008: 417-427 - [c4]Hubie Chen, Florent R. Madelaine
Quantified Constraints and Containment Problems. LICS 2008: 317-328 - 2007
- [c3]Barnaby Martin, Florent R. Madelaine
Hierarchies in Fragments of Monadic Strict NP. CiE 2007: 542-550 - [c2]Stefan S. Dantchev, Barnaby Martin
Parameterized Proof Complexity. FOCS 2007: 150-160 - 2006
- [c1]Barnaby Martin, Florent R. Madelaine
Towards a Trichotomy for Quantified H-Coloring. CiE 2006: 342-352
Parts in Books or Collections
- 2017
- [p1]Barnaby Martin
Quantified Constraints in Twenty Seventeen. The Constraint Satisfaction Problem 2017: 327-346
Editorship
- 2019
- [e1]Florin Manea, Barnaby Martin
Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019, Proceedings. Lecture Notes in Computer Science 11558, Springer 2019, ISBN 978-3-030-22995-5 [contents]
Informal and Other Publications
- 2024
- [i62]Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Mark H. Siggers, Siani Smith:
Graph Homomorphism, Monotone Classes and Bounded Pathwidth. CoRR abs/2403.00497 (2024) - [i61]Manuel Bodirsky, Marcin Kozik, Florent R. Madelaine, Barnaby Martin, Michal Wrona:
Model-checking positive equality free logic on a fixed structure (direttissima). CoRR abs/2408.13840 (2024) - 2023
- [i60]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 abs/2305.01104 (2023) - [i59]Hans L. Bodlaender
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. CoRR abs/2305.01613 (2023) - 2022
- [i58]Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen:
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. CoRR abs/2202.11595 (2022) - [i57]Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen:
Few Induced Disjoint Paths for H-Free Graphs. CoRR abs/2203.03319 (2022) - [i56]Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová:
Complexity Classification Transfer for CSPs via Algebraic Products. CoRR abs/2211.03340 (2022) - [i55]Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs. CoRR abs/2211.12203 (2022) - [i54]Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey
Complexity Framework For Forbidden Subgraphs. CoRR abs/2211.12887 (2022) - [i53]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 abs/2211.14214 (2022) - 2021
- [i52]Barnaby Martin, Daniël Paulusma, Siani Smith:
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. CoRR abs/2101.07856 (2021) - [i51]Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Depth lower bounds in Stabbing Planes for combinatorial principles. CoRR abs/2102.07622 (2021) - [i50]Dmitriy Zhuk, Barnaby Martin:
The complete classification for quantified equality constraints. CoRR abs/2104.00406 (2021) - [i49]Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma
QCSP on Reflexive Tournaments. CoRR abs/2104.10570 (2021) - [i48]Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma
Acyclic, Star, and Injective Colouring: Bounding the Diameter. CoRR abs/2104.10593 (2021) - [i47]Christoph Brause, Petr A. Golovach, Barnaby Martin, Daniël Paulusma
Partitioning H-Free Graphs of Bounded Diameter. CoRR abs/2105.04588 (2021) - [i46]Walter Kern, Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen:
Disjoint Paths and Connected Subgraphs for H-Free Graphs. CoRR abs/2105.06349 (2021) - [i45]Catarina Carvalho
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. CoRR abs/2106.13154 (2021) - [i44]Barnaby Martin, Daniël Paulusma, Siani Smith:
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter. CoRR abs/2111.11897 (2021) - [i43]Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Depth lower bounds in Stabbing Planes for combinatorial principles. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [i42]Stefan S. Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin:
Proof complexity and the binary encoding of combinatorial principles. CoRR abs/2008.02138 (2020) - [i41]Jan Bok, Nikola Jedlicková, Barnaby Martin, Daniël Paulusma, Siani Smith:
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. CoRR abs/2008.09415 (2020) - [i40]Gaétan Berthe, Barnaby Martin, Daniël Paulusma
The complexity of L(p, q)-Edge-Labelling. CoRR abs/2008.12226 (2020) - [i39]Barnaby Martin, Daniël Paulusma
Hard Problems That Quickly Become Very Easy. CoRR abs/2012.09770 (2020) - 2019
- [i38]Dmitriy Zhuk, Barnaby Martin:
QCSP monsters and the demise of the Chen Conjecture. CoRR abs/1907.00239 (2019) - [i37]Stefan S. Dantchev, Abdul Ghani, Barnaby Martin:
Sherali-Adams and the binary encoding of combinatorial principles. CoRR abs/1911.00403 (2019) - 2018
- [i36]Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen:
Disconnected Cuts in Claw-free Graphs. CoRR abs/1803.03663 (2018) - [i35]Barnaby Martin, Peter Jonsson, Manuel Bodirsky, Antoine Mottet:
Classification transfer for qualitative reasoning problems. CoRR abs/1805.02038 (2018) - [i34]Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet:
The complexity of disjunctive linear Diophantine constraints. CoRR abs/1807.00985 (2018) - [i33]Stefan S. Dantchev, Nicola Galesi, Barnaby Martin:
Resolution and the binary encoding of combinatorial principles. CoRR abs/1809.02843 (2018) - [i32]Olaf Beyersdorff, Judith Clymo, Stefan S. Dantchev, Barnaby Martin
The Riis Complexity Gap for QBF Resolution. Electron. Colloquium Comput. Complex. TR18 (2018) - [i31]Stefan S. Dantchev, Nicola Galesi, Barnaby Martin
Resolution and the binary encoding of combinatorial principles. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i30]Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma, Anthony Stewart:
Surjective H-Colouring: New Hardness Results. CoRR abs/1701.02188 (2017) - [i29]Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk:
The complexity of quantified constraints. CoRR abs/1701.04086 (2017) - [i28]Benoît Larose, Barnaby Martin, Daniël Paulusma:
Surjective H-Colouring over Reflexive Digraphs. CoRR abs/1709.09486 (2017) - 2016
- [i27]Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz:
Constraint satisfaction problems for reducts of homogeneous graphs. CoRR abs/1602.05819 (2016) - [i26]Barnaby Martin:
On the Chen Conjecture regarding the complexity of QCSPs. CoRR abs/1607.03819 (2016) - 2015
- [i25]Catarina Carvalho, Florent R. Madelaine, Barnaby Martin:
From complexity to algebra and back: digraph classes, collapsibility and the PGP. CoRR abs/1501.04558 (2015) - [i24]Manuel Bodirsky, Barnaby Martin, Antoine Mottet:
Discrete Temporal Constraint Satisfaction Problems. CoRR abs/1503.08572 (2015) - [i23]Christian Glaßer, Peter Jonsson, Barnaby Martin:
Constraint Satisfaction Problems around Skolem Arithmetic. CoRR abs/1504.04181 (2015) - [i22]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 abs/1510.02374 (2015) - [i21]Barnaby Martin, Dmitriy Zhuk:
Switchability and collapsibility of Gap Algebras. CoRR abs/1510.06298 (2015) - 2013
- [i20]Florent R. Madelaine, Barnaby Martin:
QCSP on partially reflexive cycles - the wavy line of tractability. CoRR abs/1303.0041 (2013) - [i19]Stefan S. Dantchev, Barnaby Martin:
Relativisation makes contradictions harder for Resolution. CoRR abs/1304.4287 (2013) - [i18]Barnaby Martin, Juraj Stacho:
Constraint Satisfaction with Counting Quantifiers 2. CoRR abs/1312.7605 (2013) - 2012
- [i17]Barnaby Martin:
Parameterized Proof Complexity and W[1]. CoRR abs/1203.5323 (2012) - [i16]Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma:
Finding vertex-surjective graph homomorphisms. CoRR abs/1204.2124 (2012) - [i15]Stefan S. Dantchev, Barnaby Martin:
Parameterized Resolution with bounded conjunction. CoRR abs/1204.2983 (2012) - [i14]Florent R. Madelaine, Barnaby Martin:
Containment, Equivalence and Coreness from CSP to QCSP and beyond. CoRR abs/1204.5981 (2012) - [i13]Florent R. Madelaine, Barnaby Martin:
On the complexity of the model checking problem. CoRR abs/1210.6893 (2012) - 2011
- [i12]Barnaby Martin:
Low-level dichotomy for Quantified Constraint Satisfaction Problems. CoRR abs/1102.3463 (2011) - [i11]Barnaby Martin:
QCSP on partially reflexive forests. CoRR abs/1103.6212 (2011) - [i10]Barnaby Martin, Daniël Paulusma:
The Computational Complexity of Disconnected Cut and 2K2-Partition. CoRR abs/1104.4779 (2011) - [i9]Manuel Bodirsky, Jan Kára, Barnaby Martin:
The Complexity of Surjective Homomorphism Problems -- a Survey. CoRR abs/1104.5257 (2011) - [i8]Florent R. Madelaine, Barnaby Martin, Juraj Stacho:
Constraint Satisfaction with Counting Quantifiers. CoRR abs/1112.2974 (2011) - 2010
- [i7]Florent R. Madelaine, Barnaby Martin:
The complexity of positive first-order logic without equality. CoRR abs/1003.0802 (2010) - [i6]Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker:
Distance Constraint Satisfaction Problems. CoRR abs/1004.3842 (2010) - 2009
- [i5]Barnaby Martin
The complexity of positive first-order logic without equality II: The four-element case. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - 2008
- [i4]Barnaby Martin:
Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three. CoRR abs/0808.0647 (2008) - 2007
- [i3]Barnaby Martin:
On the Complexity of a Derivative Chess Problem. CoRR abs/cs/0701049 (2007) - [i2]Stefan S. Dantchev, Barnaby Martin
Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i1]Barnaby Martin:
Dichotomies and Duality in First-order Model Checking Problems. CoRR abs/cs/0609022 (2006)
Coauthor Index
[j41] [j40] [j39] [j37] [j35] [j33] [j31] [j30] [j29] [j28] [j27] [j26] [j25] [j23] [j13] [j9] [c56] [c55] [c54] [c53] [c52] [c50] [c48] [c47] [c46] [c45] [c44] [c43] [c42] [c41] [c40] [c36] [c35] [c31] [c30] [c17] [c14] [e1] [i62] [i60] [i59] [i58] [i57] [i55] [i54] [i53] [i52] [i49] [i48] [i47] [i46] [i44] [i41] [i40] [i39] [i36] [i30] [i28] [i16] [i10]
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-05 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: