35 citations · 200 across the 47 of their papers we have counts for
6 papers · 2 filters
Exact Complexity of the Winner Problem for Young Elections
Jörg Rothe, Holger Spakowski, Jörg Vogel
In 1977, Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that bo…
Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial
Jörg Rothe
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical crypt…
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of…
Exact Complexity of Exact-Four-Colorability
Jörg Rothe
Let $M_k \seq \nats$ be a given set that consists of noncontiguous integers. Define $\exactcolor{M_k}$ to be the problem of determining whether , the chromatic number of…
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
André Grosse, Joerg Rothe, Gerd Wechsung
We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism between two isomorphic graphs is as hard as computing itself. This resul…
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Andre Grosse, Joerg Rothe, Gerd Wechsung
We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove th…