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

DOI10.1016/j.jcta.2010.06.006zbMath1225.05182OpenAlexW1930311219MaRDI QIDQ618291

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 complexityreconstructibilityline graphcombinatorial designisomorphism testinggraph isomorphism problemhypergraph isomorphism problem

Mathematics Subject Classification ID

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

Related Items (2)

Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs ⋮ Unnamed Item

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
• Graph isomorphism problem
• Concerning the complexity of deciding isomorphism of block designs
• Group-theoretic algorithms and graph isomorphism
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• An extension of the Erdoes, Ko, Rado theorem to t-designs
• An optimal lower bound on the number of variables for graph identification
• On t-designs
• 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
• A note on optimal unimodular lattices
• A hole-size bound for incomplete t-wise balanced designs
• Coding Theory and Algebraic Combinatorics
• Combinatorial Designs for Authentication and Secrecy Codes
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Isomorphism of graphs which are pairwise k-separable
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• The graph isomorphism disease
• The Steiner triple systems of order 19
• Reconstructing Extended Perfect Binary One-Error-Correcting Codes From Their Minimum Distance Graphs
• On the n^{log n} isomorphism technique (A Preliminary Report)
• Flag-transitive Steiner Designs
• An Efficient Algorithm for Graph Isomorphism
• Logical Approaches to Computational Barriers

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