# Local algorithms for the maximum flow and minimum cut in bounded-degree networks

Preprint · Endre Csóka, András Pongrácz

- Archive id: arxiv:1005.0513
- Published: 2010-05-04
- arXiv: https://arxiv.org/abs/1005.0513
- Source URL: https://arxiv.org/abs/1005.0513
- PDF: https://arxiv.org/pdf/1005.0513
- Provenance: arxiv

## Abstract

We show a deterministic constant-time local algorithm for constructing an approximately maximum flow and minimum fractional cut in multisource-multitarget networks with bounded degrees and bounded edge capacities. Locality means that the decision we make about each edge only depends on its constant radius neighborhood. We show two applications of the algorithms: one is related to the Aldous-Lyons Conjecture, and the other is about approximating the neighborhood distribution of graphs by bounded-size graphs. The scope of our results can be extended to unimodular random graphs and networks. As a corollary, we generalize the Maximum Flow Minimum Cut Theorem to unimodular random flow networks.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.