Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-011 | 21st November 2007 00:00

The Complexity of the Hajos Calculus for Planar Graphs

RSS-Feed




TR08-011
Authors: Kazuo Iwama, Suguru Tamaki
Publication: 25th February 2008 12:11
Downloads: 1662
Keywords: 


Abstract:

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajĀLos calculus is polynomially bounded.



ISSN 1433-8092 | Imprint