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
Pages
16
From page
103
To page
118
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
Serial Year
2007
Journal title
Discrete Applied Mathematics
Record number
886403
Link To Document