On the complexity of graph reconstruction
From MaRDI portal
Publication:4298372
DOI10.1007/BF01578845zbMath0806.05051MaRDI QIDQ4298372
Hemaspaandra, Lane A., Dieter Kratsch
Publication date: 14 February 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Complexity results in graph reconstruction, Reconstruction of Interval Graphs, Reconstruction of interval graphs, Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs, Unnamed Item, The robustness of LWPP and WPP, with an application to graph reconstruction, Towards the reconstruction of posets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstructibility and perfect graphs
- A congruence theorem for trees
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- The complexity of combinatorial problems with succinct input representation
- Does co-NP have short interactive proofs ?
- Graph isomorphism is in the low hierarchy
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Proof of Harary's conjecture on the reconstruction of trees
- A comparison of polynomial time reducibilities
- On log-tape isomorphisms of complete sets
- Gap-definable counting classes
- The reconstruction of outerplanar graphs
- On Ulam's conjecture for separable graphs
- Reconstruction of maximal outerplanar graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- The NP-completeness column: an ongoing guide
- Relativization of questions about log space computability
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- Graph reconstruction—a survey
- Nearly acyclic graphs are reconstructible
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- Polynomial Time Enumeration Reducibility
- Reconstruction of Cacti
- A technique for reconstructing disconnected graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
