Determinant Algorithms for Random Planar Structures

David Bruce Wilson

Colbourn, Myrvold, and Neufeld developed a fast algorithm for generating random arborescences of a graph, using the fact that the determinant of a certain matrix enumerates these arborescenes. There are a variety of other combinatorial structures that can be enumerated by evaluating a determinant, structures of interest in both the physics and mathematical communities. Randomly generating such objects has been a useful tool in studying their properties, and has guided mathematicians by suggesting theorems that might be true. We show here how to adapt and extend the techniques used by Colbourn et al. to efficiently randomly generate such objects. These new algorithms offer significant improvements over previous algorithms in both their generality and their speed.

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pp. 258-267, 1997.
PostScript version
conference slides

Scanned version in the ACM's Digital Library

Copyright © 1997 by ACM, Inc.