Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with combinatorial problems:
TR95-047 | 5th October 1995
Martin Loebbing, Ingo Wegener

The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

An increasing number of results in graph theory, combinatorics and
theoretical computer science is obtained with the help of computers,
e.g. the proof of the Four Colours Theorem or the computation of
certain Ramsey numbers. Binary decision diagrams, known as tools in
hardware verification ... more >>>

TR96-043 | 16th August 1996
Edmund Ihler

On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

ISSN 1433-8092 | Imprint