The Max-Flow Min-Cut theorem for countable networks

DOI10.1016/J.JCTB.2010.08.002MaRDI QIDQ618031zbMATH OpenOpenAlexFDO

Authors 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)

Full work available at URL https://arxiv.org/abs/0911.4003

zbMATH Keywords

networksinfinite graphsflowsends of graphsMax-Flow Min-Cut

Mathematics Subject Classification ID

Flows in graphs (05C21) Connectivity (05C40) Infinite graphs (05C63)

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.

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

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 970819 (Why is no real title available?)
• Menger's theorem for graphs containing no infinite paths
• Menger's theorem for infinite graphs

Cited in

(19)

• Minimum spanning trees in infinite graphs: theory and algorithms
• (Towards a) statistical probabilistic lazy lambda calculus
• The Lovász-Cherkassky theorem in infinite graphs
• Random walks in random Dirichlet environment are transient in dimension \(d \geq 3\)
• Borel circle squaring
• On packing and covering polyhedra in infinite dimensions
• scientific article; zbMATH DE number 3860851 (Why is no real title available?)
• A general framework for probabilistic characterizing formulae
• Relational \(\star\)-liftings for differential privacy
• 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
• Probabilistic functions and cryptographic oracles in higher order logic
• A measure-theoretical max-flow-min-cut problem
• A greedy algorithm for finding maximum spanning trees in infinite graphs
• Algebraic flow theory of infinite graphs
• The max-flow min-cut property and \(\pm 1\)-resistant sets
• Random walks in Dirichlet environment: an overview. Dedicated to Dominique Bakry on the occasion of his 60th birthday
• A theory of composition for differential obliviousness
• A simplex method for uncapacitated pure-supply infinite network flow problems

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)