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

DOI10.1016/j.jcta.2010.06.006zbMath1225.05182MaRDI 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 complexity; reconstructibility; line graph; combinatorial design; isomorphism testing; graph isomorphism problem; hypergraph isomorphism problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05B05: Combinatorial aspects of block designs

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C76: Graph operations (line graphs, products, etc.)

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