Exponential lower bounds for the tree-like Hajós calculus

DOI10.1016/0020-0190(95)00035-BzbMath0875.68687OpenAlexW1987569957MaRDI QIDQ673010

Kazuo Iwama, Toniann Pitassi

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00035-b

zbMATH Keywords

Lower boundsTheory of computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ The complexity of the Hajós calculus for planar graphs

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• Some Colouring Problems and their Complexity
• The relative efficiency of propositional proof systems

This page was built for publication: Exponential lower bounds for the tree-like Hajós calculus