Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
NIST Authors in Bold
|Author(s):||Brian D. Cloteaux;|
|Title:||Approximating the Number of Bases for Almost All Matroids|
|Published:||February 01, 2011|
|Abstract:||We define a class of matroids A for which a fully polynomial randomized approximation scheme (fpras) exists for counting the number of bases of the matroids. We then show that as the number of elements in a matroid increases, the probability that a matroid belongs to A goes to 1. We thus provide a fpras for counting the number of bases that applies to almost all matroids.|
|Pages:||pp. 149 - 154|
|Keywords:||matroids, randomized algorithms|
|PDF version:||Click here to retrieve PDF version of paper (103KB)|