Complexity results in graph reconstruction
From MaRDI portal
Publication:867853
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
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
