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.