Approximately counting bases of bicircular matroids

Heng Guo, Mark Jerrum

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)124 - 135
Number of pages12
JournalCombinatorics, Probability and Computing
Volume30
Issue number1
Early online date6 Aug 2020
DOIs
Publication statusPublished - 1 Jan 2021

Fingerprint Dive into the research topics of 'Approximately counting bases of bicircular matroids'. Together they form a unique fingerprint.

Cite this