Approximately counting bases of bicircular matroids

Heng Guo; Mark Jerrum

doi:10.1017/S0963548320000292

Approximately counting bases of bicircular matroids

Heng Guo, Mark Jerrum

Research output: Contribution to journal › Article › peer-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 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	https://doi.org/10.1017/S0963548320000292
Publication status	Published - 1 Jan 2021

Access to Document

10.1017/S0963548320000292Licence: All Rights Reserved

bicircular-CPCv2Accepted author manuscript, 163 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/approximately-counting-bases-of-bicircular-matroids/1503038473E8C262382C9D231718F2DFLicence: All Rights Reserved

Cite this

@article{b3950cc962734ef2abf3bb61827411d3,

title = "Approximately counting bases of bicircular matroids",

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.",

author = "Heng Guo and Mark Jerrum",

year = "2021",

month = jan,

day = "1",

doi = "10.1017/S0963548320000292",

language = "English",

volume = "30",

pages = "124 -- 135",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "1",

}

TY - JOUR

T1 - Approximately counting bases of bicircular matroids

AU - Guo, Heng

AU - Jerrum, Mark

PY - 2021/1/1

Y1 - 2021/1/1

N2 - 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.

AB - 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.

U2 - 10.1017/S0963548320000292

DO - 10.1017/S0963548320000292

M3 - Article

SN - 0963-5483

VL - 30

SP - 124

EP - 135

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 1

ER -

Approximately counting bases of bicircular matroids

Abstract

Access to Document

Fingerprint

Cite this