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…