Computational complexity of reconstruction and isomorphism testing for designs and line graphs

DOI10.1016/J.JCTA.2010.06.006MaRDI QIDQ618291zbMATHOpenAlexFDO

Authors Michael Huber

Publication date 14 January 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcta.2010.06.006

zbMATH Keywords

computational complexityline graphcombinatorial designreconstructibilityisomorphism testinggraph isomorphism problemhypergraph isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of block designs (05B05) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Quasipolynomial-time canonical form for steiner designs
• On testing isomorphism of graphs of bounded eigenvalue multiplicity
• scientific article; zbMATH DE number 1256777
• Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM

Cites work

• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 3961622 (Why is no real title available?)
• scientific article; zbMATH DE number 3663155 (Why is no real title available?)
• scientific article; zbMATH DE number 3664988 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256777 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1382769 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• scientific article; zbMATH DE number 910921 (Why is no real title available?)
• scientific article; zbMATH DE number 3893215 (Why is no real title available?)
• A hole-size bound for incomplete \(t\)-wise balanced designs
• A note on optimal unimodular lattices
• An Efficient Algorithm for Graph Isomorphism
• An extension of the Erdoes, Ko, Rado theorem to t-designs
• An optimal lower bound on the number of variables for graph identification
• Coding theory and algebraic combinatorics
• Combinatorial designs for authentication and secrecy codes
• Concerning the complexity of deciding isomorphism of block designs
• Flag-transitive Steiner Designs
• Graph isomorphism problem
• Group-theoretic algorithms and graph isomorphism
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism of graphs which are pairwise k-separable
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Logical Approaches to Computational Barriers
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On t-designs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• Reconstructing Extended Perfect Binary One-Error-Correcting Codes From Their Minimum Distance Graphs
• The CRC handbook of combinatorial designs
• The Steiner triple systems of order 19
• The graph isomorphism disease

Cited in

(3)

• Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
• Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems
• On the complexity of identifying strongly regular graphs

This page was built for publication: Computational complexity of reconstruction and isomorphism testing for designs and line graphs

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