Random sampling in residual graphs

DOI10.1145/509907.509918MaRDI QIDQ3579176zbMATH OpenOpenAlexFDO

Authors Matthew S. Levine, David R. Karger

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/509907.509918

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cited in

(7)

• On computing minimum(s,t)-cuts in digraphs
• Maximum bipartite flow in networks with adaptive channel width
• Weighted random sampling with a reservoir
• Sparsification of two-variable valued constraint satisfaction problems
• Sparsification of directed graphs via cut balance
• Deterministic maximum flows in simple graphs
• Fast augmenting paths by random sampling from residual graphs

This page was built for publication: Random sampling in residual graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579176)