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