Title of article :
Complexity results in graph reconstruction Original Research Article
Author/Authors :
Edith Hemaspaandra، نويسنده , , Lane A. Hemaspaandra، نويسنده , , Stanis?aw P. Radziszowski، نويسنده , , Rahul Tripathi، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Abstract :
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 (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts image of deletion:
Keywords :
Reconstruction numbers , Legitimate deck , Graph reconstruction , Graph isomorphism
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics
