Complexity results in graph reconstruction

DOI10.1016/j.dam.2006.04.038zbMath1117.05078MaRDI QIDQ867853

Hemaspaandra, Lane A., Edith Hemaspaandra, Rahul Tripathi, Stanislaw P. Radziszowski

Publication date: 19 February 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.038

zbMATH Keywords

graph isomorphism; legitimate deck; reconstruction numbers

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A congruence theorem for trees
• A low and a high hierarchy within NP
• Graph isomorphism is in the low hierarchy
• Proof of Harary's conjecture on the reconstruction of trees
• On log-tape isomorphisms of complete sets
• Parallel concepts in graph theory
• Some basic observations on Kelly's conjecture for graphs
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• Graph Isomorphism is in SPP
• On Ulam's conjecture for separable graphs
• On a conjecture concerning the reconstruction of graphs
• The ally-reconstruction number of a tree with five or more vertices is three
• The Multiple Sequence Alignment Problem in Biology
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The graph reconstruction number
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Graph reconstruction—a survey
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• On the complexity of graph reconstruction
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Threshold Computation and Cryptographic Security
• The Reconstruction of a Tree from its Maximal Subtrees
• On Reconstructing a Graph
• The complexity theory companion
• Graph reconstruction from subgraphs