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

DOI10.1016/J.JCTA.2010.06.006zbMATH Open1225.05182OpenAlexW1930311219MaRDI QIDQ618291FDOQ618291

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

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

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)

Cites Work

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

Cited In (2)

• Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
• Title not available (Why is that?)

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)