11 citations · 18 across the 6 of their papers we have counts for
22 papers
The Complexity of Kings
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely orient…
Dichotomy for Voting Systems
Edith Hemaspaandra, Lane A. Hemaspaandra
Scoring protocols are a broad class of voting systems. Each is defined by a vector , , of integers such that each voter contribu…
Isomorphic Implication
Michael Bauland, Edith Hemaspaandra
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set…
All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diago…
Complexity Results in Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski +1
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs…
Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas
Edith Hemaspaandra
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems, showed that a…