The Max-Flow Min-Cut theorem for countable networks
From MaRDI portal
Publication:618031
DOI10.1016/J.JCTB.2010.08.002zbMATH Open1221.05186arXiv0911.4003OpenAlexW2008634162MaRDI QIDQ618031FDOQ618031
Ron Aharoni, Eli Berger, Amitai Perlstein, Philipp Sprüssel, Agelos Georgakopoulos
Publication date: 14 January 2011
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are "orthogonal" to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff's first law also for ends.
Full work available at URL: https://arxiv.org/abs/0911.4003
Recommendations
- A measure-theoretical max-flow-min-cut problem
- A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory
- Max-flow min-cut theorem in an anisotropic network
- On Gale's feasibility theorem for certain infinite networks
- scientific article; zbMATH DE number 997341
Cites Work
Cited In (19)
- Probabilistic Functions and Cryptographic Oracles in Higher Order Logic
- A Simplex Method for Uncapacitated Pure-supply Infinite Network Flow Problems
- A greedy algorithm for finding maximum spanning trees in infinite graphs
- The max-flow min-cut property and \(\pm 1\)-resistant sets
- A measure-theoretical max-flow-min-cut problem
- Random walks in Dirichlet environment: an overview. Dedicated to Dominique Bakry on the occasion of his 60th birthday
- A General Framework for Probabilistic Characterizing Formulae
- On packing and covering polyhedra in infinite dimensions
- A theory of composition for differential obliviousness
- (Towards a) statistical probabilistic lazy lambda calculus
- Minimum spanning trees in infinite graphs: theory and algorithms
- Random walks in random Dirichlet environment are transient in dimension \(d \geq 3\)
- Borel circle squaring
- A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory
- Locally finite graphs with ends: A topological approach. II: Applications
- The Lovász-Cherkassky theorem in infinite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algebraic flow theory of infinite graphs
This page was built for publication: The Max-Flow Min-Cut theorem for countable networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q618031)
