On the complexity of graph reconstruction
From MaRDI portal
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- A congruence theorem for trees
- A low and a high hierarchy within NP
- A technique for reconstructing disconnected graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Computational Complexity of Probabilistic Turing Machines
- Does co-NP have short interactive proofs ?
- Gap-definable counting classes
- Graph isomorphism is in the low hierarchy
- Graph reconstruction—a survey
- scientific article; zbMATH DE number 3141308 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3865328 (Why is no real title available?)
- scientific article; zbMATH DE number 3906520 (Why is no real title available?)
- scientific article; zbMATH DE number 3936518 (Why is no real title available?)
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 4077274 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3685512 (Why is no real title available?)
- scientific article; zbMATH DE number 3458693 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 3258862 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- scientific article; zbMATH DE number 3339171 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- Nearly acyclic graphs are reconstructible
- On Isomorphisms and Density of NP and Other Complete Sets
- On log-tape isomorphisms of complete sets
- On Ulam's conjecture for separable graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Polynomial Time Enumeration Reducibility
- Proof of Harary's conjecture on the reconstruction of trees
- Reconstructibility and perfect graphs
- Reconstruction of Cacti
- Reconstruction of maximal outerplanar graphs
- Reductions among polynomial isomorphism types
- Relativization of questions about log space computability
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Strong nondeterministic polynomial-time reducibilities
- The complexity of combinatorial problems with succinct input representation
- The NP-completeness column: an ongoing guide
- The reconstruction of outerplanar graphs
Cited in
(17)- Towards the reconstruction of posets
- The robustness of LWPP and WPP, with an application to graph reconstruction
- On the reconstruction of planar graphs
- On Reconstructing Graphs and Their Complements
- On the complexity of reconstructing H-free graphs from their Star Systems
- scientific article; zbMATH DE number 3841911 (Why is no real title available?)
- scientific article; zbMATH DE number 4023330 (Why is no real title available?)
- On the Algorithmic Complexity of Minkowski's Reconstruction Theorem
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Network Reconstruction – A New Approach to the Traveling Salesman Problem and Complexity
- Mathematical Foundations of Computer Science 2004
- Reconstruction of Interval Graphs
- Algorithms and Computation
- Reconstruction of interval graphs
- Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
- Complexity results in graph reconstruction
- Reconstructing graphs from cut-set sizes
This page was built for publication: On the complexity of graph reconstruction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4298372)
