Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kazuo Iwama:

TR08-011 | 21st November 2007
Kazuo Iwama, Suguru Tamaki

The Complexity of the Hajos Calculus for Planar Graphs

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.

more >>>

TR06-112 | 22nd August 2006
Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

Strip Packing vs. Bin Packing

In this paper
we establish a general algorithmic framework between bin packing
and strip packing, with which we achieve the same asymptotic
bounds by applying bin packing algorithms to strip packing. More
precisely we obtain the following results: (1) Any offline bin
packing algorithm can be applied to strip packing ... more >>>

TR03-053 | 8th July 2003
Kazuo Iwama, Suguru Tamaki

Improved Upper Bounds for 3-SAT

This paper presents a new upper bound for the
$k$-satisfiability problem. For small $k$'s, especially for $k=3$,
there have been a lot of algorithms which run significantly faster
than the trivial $2^n$ bound. The following list summarizes those
algorithms where a constant $c$ means that the algorithm runs in time
more >>>

ISSN 1433-8092 | Imprint