## Determinant Algorithms for Random Planar Structures

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.