A parallelization of Miller's n^ n isomorphism technique

DOI10.1016/0020-0190(92)90243-OMaRDI QIDQ1198063zbMATH OpenOpenAlexFDO

Authors Charles J. Colbourn, Luc Teirlinck, D. R. Stinson

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90243-o

zbMATH Keywords

complexityisomorphismparallel algorithmssequential algorithmSteiner triple systems

Mathematics Subject Classification ID

Triple systems (05B07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Loops, quasigroups (20N05) Distributed algorithms (68W15)

Review text

The authors first present G. L. Miller's sequential algorithm of complexity \(O(n^{\log n+c})\) for isomorphism testing of Steiner triple systems of order \(n\), \(\text{STS}(n)\), as Algorithm Canonical, a recursive procedure returning a canonical form of an \(\text{STS}(n)\). Two main steps in the algorithm have been called forcing and choosing and the forcing step is shown as the computation of a closure of a set defined in a suitable way needing at most \(3\log n\) iterations. The algorithm is then parallelized using a CREW-PRAM model needing \(O(n^{\log n+2})\) processors and a total running time of \(O((\log n)^ 2)\). Whether the problem lies in NC is left open. It is also shown that both the sequential and parallel algorithms can be generalized to compute canonical forms of quasi-semigroups.

Recommendations

• scientific article; zbMATH DE number 3933088
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• Parallel Tree Contraction Part 2: Further Applications
• Quasipolynomial-time canonical form for steiner designs
• A Randomized Parallel Algorithm for Planar Graph Isomorphism

Cites work

• Concerning the complexity of deciding isomorphism of block designs
• Embedding Partial Steiner Triple Systems
• scientific article; zbMATH DE number 3933088 (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 3728314 (Why is no real title available?)
• Implementation of simultaneous memory address access in models that forbid it
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• Sorting in \(c \log n\) parallel steps

Cited in

(3)

• scientific article; zbMATH DE number 3933088 (Why is no real title available?)
• Steiner triple systems of order 19 with nontrivial automorphism group
• On the \(n\log{n}\) isomorphism technique (preliminary report)

This page was built for publication: A parallelization of Miller's \(n^{\log n}\) isomorphism technique

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