Criss-cross algorithm: Difference between revisions

Revision as of 15:05, 19 August 2014

Revision as of 17:27, 30 September 2014

Line 47:

===Oriented matroids===

[[File:max-flow min-cut example.svg|frame|right|The [[max-flow min-cut theorem]] states that athe networkmaximum withflow thethrough valuea of flownetwork equalis toexactly the capacity of anits s-tminimum cut. This theorem can be proved using the criss-cross algorithm for oriented matroids.]]

The criss-cross algorithm is often studied using the theory of [[oriented matroid]]s (OMs), which is a [[combinatorics|combinatorial]] abstraction of linear-optimization theory.<ref name="OMBook"/><ref>The theory of [[oriented matroid]]s was initiated by [[R.&nbsp;Tyrrell Rockafellar]]. {{harv|Rockafellar|1969}}:<p>{{cite book

|first=R.&nbsp;T.