Publications
2006
On Computing the Smallest Four-Coloring of Planar Graphs and Non-Self-Reducible Sets in P.
A. Große, J. Rothe, and G. Wechsung.
Information Processing Letters, vol. 99, no. 6, pp. 215-221, September 2006. [pdf]
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
R.A.I.R.O. Theoretical Informatics and Applications, vol. 40, no. 1, pp. 75-91, January 2006. [pdf]
If P ≠ NP then Some Strongly Noninvertible Functions are Invertible.
L. Hemaspaandra, K. Pasanen, and J. Rothe.
Theoretical Computer Science, vol. 362, no. 1-3, pp. 54-62, October 2006. [pdf]
2003
Exact Complexity of Exact-Four-Colorability.
J. Rothe.
Information Processing Letters, vol. 87, no. 1, pp. 7-12, July 2003. [pdf]
2002
Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.
J. Rothe, H. Spakowski, and J. Vogel.
Proceedings of the Second IFIP International Conference on Theoretical Computer Science (TCS 2002), which was held as Stream 1 of the 17th World Computer Congress, Montréal, Quebéc, Canada. Kluwer Academic Publishers, pages 310-322, August 2002.
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), Cesky Krumlov, Czech Republic.
Springer-Verlag Lecture Notes in Computer Science 2573, pages 258-269, June 2002.
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.
A. Große, J. Rothe, and G. Wechsung.
Theory of Computing Systems, vol. 35, no. 1, pp. 81-93, February 2002. [pdf]
2001
Kryptographische Protokolle und Null-Information.
J. Rothe.
Informatik Spektrum, vol. 25, no. 2, pp. 120-131, April 2002. In German.
Appears also in: Jahrbuch der Heinrich-Heine-Universität Düsseldorf 2001, pp. 183-201, Düsseldorf, 2001.
Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
A. Große, J. Rothe, and G. Wechsung.
Proceedings of the Proceedings of the Seventh International Italian Conference on Theoretical Computer Science (ICTCS 2001), Torino, Italia.
Springer-Verlag Lecture Notes in Computer Science 2202, pages 339-356, October 2001.
If P ≠ NP then Some Strongly Noninvertible Functions are Invertible.
L. Hemaspaandra, K. Pasanen, and J. Rothe.
Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001), Riga, Latvia.
Springer-Verlag Lecture Notes in Computer Science 2138, pages 162-171, August 2001.
Exact Complexity of Exact-Four-Colorability.
J. Rothe.
Technical Report cs.CC/0109018, ACM Computing Research Repository (CoRR), 5 pages, September 2001.
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.
A. Große, J. Rothe, and G. Wechsung.
Technical Report cs.CC/0106041, ACM Computing Research Repository (CoRR), 12 pages, June 2001.
Revises Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/23, 14 pages, August 2000.
Kryptographische Protokolle und Null-Information.
J. Rothe.
Jahrbuch der Heinrich-Heine-Universität Düsseldorf 2001, pp. 183-201, Düsseldorf, 2001. In German.
Appears also in: Informatik Spektrum, Springer-Verlag, vol. 25, no. 2, pp. 120-131, April 2002.
2000
Restrictive Acceptance Suffices for Equivalence Problems.
B. Borchert, L. Hemaspaandra, and J. Rothe.
London Mathematical Society Journal of Computation and Mathematics, vol. 3, pp. 86-95, March 2000.
Heuristics versus Completeness for Graph Coloring.
J. Rothe.
Chicago Journal of Theoretical Computer Science, vol. 2000, article 1, 16 pages, February 2000.
If P ≠ NP then Some Strongly Noninvertible Functions are Invertible.
L. Hemaspaandra, K. Pasanen, and J. Rothe.
Technical Report cs.CC/0010011, ACM Computing Research Repository (CoRR), 9 pages, October 2000.
Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
A. Große, J. Rothe, and G. Wechsung.
Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/23, 14 pages, August 2000.