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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.jctb.2010.08.002 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
orthogonal pair,ends of graphs,finite network,countable network,networks,flows,infinite graphs,max-flow min-cut theorem,reverse cut,finite path,max-flow min-cut,mundane flow,strong version,satisfiability,max flow min cut | Cut,Discrete mathematics,Combinatorics,Countable set,Max-flow min-cut theorem,Flow (psychology),Mathematics,Maximum cut | Journal |
Volume | Issue | ISSN |
101 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
6 | 0.44 | 3 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ron Aharoni | 1 | 380 | 66.56 |
Eli Berger | 2 | 182 | 52.72 |
Agelos Georgakopoulos | 3 | 66 | 12.05 |
Amitai Perlstein | 4 | 11 | 1.39 |
Philipp Sprüssel | 5 | 46 | 8.52 |