Complexity results in graph reconstruction

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

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

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 isomorphismlegitimate deckreconstruction numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Reconstruction of interval graphs ⋮ Unnamed Item ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction

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

This page was built for publication: Complexity results in graph reconstruction