Cutting planes width and the complexity of graph isomorphism refutations

DOI10.4230/LIPICS.SAT.2023.26MaRDI QIDQ6643111zbMATH OpenFDO

Authors Jacobo Torán, Florian Wörz

Publication date 26 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.SAT.2023.26

zbMATH Keywords

combinatorial optimizationcutting planesgraph isomorphismlinear programmingproof complexityWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cited in

(1)

• Supercritical size-width tree-like resolution trade-offs for graph isomorphism

This page was built for publication: Cutting planes width and the complexity of graph isomorphism refutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6643111)