Complexity results in graph reconstruction

DOI10.1016/J.DAM.2006.04.038MaRDI QIDQ867853zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Rahul Tripathi, Lane A. Hemaspaandra, Stanisław 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 isomorphismlegitimate deckreconstruction numbers

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 3906536
• On the complexity of graph reconstruction
• scientific article; zbMATH DE number 1051281
• scientific article; zbMATH DE number 3841911
• The vertex and edge graph reconstruction numbers of small graphs
• Reconstruction of small graphs and digraphs
• On the reconstruction of the matching polynomial and the reconstruction conjecture
• The edge reconstruction number of a disconnected graph
• Graph reconstruction -- some new developments

Cites work

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

Cited in

(7)

• The robustness of LWPP and WPP, with an application to graph reconstruction
• scientific article; zbMATH DE number 3841911 (Why is no real title available?)
• On the complexity of graph reconstruction
• The robustness of LWPP and WPP, with an application to graph reconstruction
• Mathematical Foundations of Computer Science 2004
• Reconstruction of interval graphs
• Coloring graphs as complete graph invariants

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q867853)