Abstract
We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in bicircular matroids. This is a natural class of matroids for which counting bases exactly is #P-hard and yet approximate counting can be done efficiently.
| Original language | English |
|---|---|
| Pages (from-to) | 124 - 135 |
| Number of pages | 12 |
| Journal | Combinatorics, Probability and Computing |
| Volume | 30 |
| Issue number | 1 |
| Early online date | 6 Aug 2020 |
| DOIs | |
| Publication status | Published - 1 Jan 2021 |