4 papers
Approximating two-terminal network reliability
Weiming Feng, Yucheng Fu, Heng Guo
We present a fully polynomial-time randomised approximation scheme (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. We also show th…
Fast counting and sampling for ferromagnetic two-spin systems
Weiming Feng, Heng Guo, Yichun Yang
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an effic…
Rapid mixing of the flip chain over non-crossing spanning trees
Konrad Anand, Weiming Feng, Graham Freifeld +3
We show that the flip chain for non-crossing spanning trees of points in convex position mixes in time . We use connections between Fuss-Catalan structures to c…
Approximate Counting for Spin Systems in Sub-Quadratic Time
Konrad Anand, Weiming Feng, Graham Freifeld +2
We present two randomised approximate counting algorithms with running time for some constant and accuracy : (1) for the h…