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

DOI10.1016/0020-0190(95)00035-BzbMATH Open0875.68687OpenAlexW1987569957MaRDI QIDQ673010FDOQ673010

Authors: 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

Recommendations

• The Complexity of the Hajós Calculus
• scientific article; zbMATH DE number 1256654
• The complexity of the Hajós calculus for planar graphs
• A lower bound for tree resolution
• scientific article; zbMATH DE number 4002120

zbMATH Keywords

Lower boundsTheory of computation

Mathematics Subject Classification ID

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

Cites Work

• Some simplified NP-complete graph problems
• The relative efficiency of propositional proof systems
• Some Colouring Problems and their Complexity
• Title not available (Why is that?)

Cited In (3)

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

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

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