All reports by Author Tobias Riege:

__
TR06-078
| 12th June 2006
__

Tobias Riege, Jörg Rothe#### Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

Revisions: 1

__
TR06-036
| 7th February 2006
__

Tobias Riege, Jörg Rothe#### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

__
TR05-146
| 25th November 2005
__

Gábor Erdèlyi, Tobias Riege, Jörg Rothe#### Quantum Cryptography: A Survey

Revisions: 2

__
TR02-068
| 10th December 2002
__

Tobias Riege, Jörg Rothe#### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

Tobias Riege, Jörg Rothe

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

Tobias Riege, Jörg Rothe

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

Gábor Erdèlyi, Tobias Riege, Jörg Rothe

We survey some results in quantum cryptography. After a brief

introduction to classical cryptography, we provide the physical and

mathematical background needed and present some fundamental protocols

from quantum cryptography, including quantum key distribution and

quantum bit commitment protocols.

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>