No label defined (Q3330973)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3862930
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3862930

      Statements

      1983
      0 references
      Min-max relations in combinatorial optimization
      0 references
      max-flow min-cut theorem
      0 references
      survey
      0 references
      total unimodularity
      0 references
      total dual integrality
      0 references
      blocking and anti-blocking polyhedra
      0 references
      bipartite graphs
      0 references
      network flows
      0 references
      matchings
      0 references
      multicommodity flows
      0 references
      arborescences
      0 references
      directed cuts
      0 references
      perfect graphs
      0 references
      clutters
      0 references
      blockers
      0 references
      matroids
      0 references
      submodular functions
      0 references
      [For the entire collection see Zbl 0533.00035.] Min-max relations in combinatorial optimization (typical example: Ford- Fulkerson's max-flow min-cut theorem) are of use in studying algorithms (they can serve as an optimality criterion, and they often follow as a by-product of an algorithm), and have theoretical interest (they often imply a ''polyhedral'' characterization). This paper gives a survey of min- max relations in combinatorial optimization. After introduction and preliminaries, it briefly reviews some methods: total unimodularity; total dual integrality; and blocking and anti-blocking polyhedra. Next the survey of results is centered around the following notions: bipartite graphs; network flows; matchings and generalizations; multicommodity flows; arborescences and directed cuts; perfect graphs; clutters and blockers; matroids and submodular functions. Some proofs are given, if they are illustrative for a typical method.
      0 references

      Identifiers

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