A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time (Q750277)

From MaRDI portal
Revision as of 08:28, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
scientific article

    Statements

    A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time (English)
    0 references
    0 references
    0 references
    1990
    0 references
    Given is a network with n nodes and m arcs. The authors describe the first primal simplex algorithm for the maximum flow problem which is strongly polynomial. It relies on the fact that among the variables which might enter a basis one is chosen, whose corresponding arc is closest to the source. In this case a maximum flow will be found after at most \(n\cdot m\) pivots. The authors describe also an \(O(n^ 2m)\) implementation of their new method.
    0 references
    primal simplex algorithm
    0 references
    strongly polynomial
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references