Publications
Refereed Journal Publications
Quantum Cryptography: A Survey.
D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.
ACM Computing Surveys, vol. 39, no. 2, article 6, 27 pp., June 2007.
An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Information Processing Letters, vol. 101, no. 3, pp. 101-106, February 2007.
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Theory of Computing Systems, vol. 39, no. 5, pp. 635-668, September 2006.
On-line publication DOI 10.1007/s00224-004-1209-8, December 2004. [pdf]
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey.
T. Riege and J. Rothe.
Journal of Universal Computer Science, vol. 12, no. 5, pp. 551-578, May 2006.
Refereed Publications in Conference Proceedings
An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Proceedings of the Second IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2006), Damascus, Syria. IEEE Computer Society Press, pages 1021-1022, April 2006.
Also presented at the ICALP Affiliated Workshop for Improving Exponential-Time Algorithms (iETA'06), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 53-58. Venice, Italy, July 2006.
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.
T. Riege and J. Rothe.
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland.
Springer-Verlag Lecture Notes in Computer Science 3618, pages 733-744, August 2005.
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Proceedings of the First IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2004), Damascus, Syria. IEEE Computer Society Press, pages 653-654, April 2004. A six-page extended abstract is available from CD-ROM ISBN 0-7803-8483-0.
Invited Contributions to Journals, Conferences, Workshops, etc.
Improving Exponential-Time Algorithms for NP-Complete Problems.
T. Riege and J. Rothe.
Invited talk at the ICALP Affiliated Workshop for Improving Exponential-Time Algorithms (iETA'06), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 65-76. Venice, Italy, July 2006.
Quantenkryptographie.
G. Erdélyi, T. Riege, and J. Rothe.
Invited talk at the Kutatasok 2005 az Eötvös Jozsef Föiskolan, Steinerne Molnar Judit, editor, pages 411-432. Baja, Hungary, November 2005.
Additional Journal and Other Publication
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
T. Riege and J. Rothe.
Journal of Universal Computer Science, vol. 12, no. 6, pp. 725-744, June 2006.
Special issue: Computational Challenges of Massive Data Sets and Randomness in Computation, J. Rothe and H. Arimura, editors. Selected contributions from the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS).
Technical Reports
Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
T. Riege and J. Rothe.
Technical Report TR06-078, Electronic Colloquium on Computational Complexity (ECCC), 16 pages, June 2006.
An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Technical Report cs.CC/0603060, ACM Computing Research Repository (CoRR), 9 pages, March 2006.
Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
T. Riege and J. Rothe.
Technical Report TR06-036, Electronic Colloquium on Computational Complexity (ECCC), 24 pages, March 2006.
Quantum Cryptography: A Survey.
D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.
Technical Report TR05-146, Electronic Colloquium on Computational Complexity (ECCC), 25 pages, March 2006.
Extends the December 2005 version of TR05-146 (ECCC).
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.
T. Riege and J. Rothe.
Technical Report cs.CC/0506090, ACM Computing Research Repository (CoRR), 20 pages, June 2005.
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Technical Report cs.CC/0212016-v3,ACM Computing Research Repository (CoRR), 38 pages, March 2004.
Revises and extends the Technical Report cs.CC/0212016-v1, ACM Computing Research Repository (CoRR), 15 pages, December 2002.
PhD Thesis
The Domatic Number Problem: Boolean Hierarchy Completeness and Exact Exponential-Time Algorithms.
T. Riege.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 109 pages, November 2006.
Diploma Thesis
Vollständige Probleme in der Booleschen Hierarchie über NP.
T. Riege.
Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 51 pages, August 2002.