rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Programming in networks and graphs
    sub title: on the combinatorial background and near-equivalence of network flow and matching algorithms
  name:
    name part: Derigs, Ulrich
    name part: 1950-
    role:
      role term: creator
  name:
    name part: SpringerLink (Online service)
  type of resource: text
  genre: bibliography
  genre: Electronic books.
  origin info:
    place:
      place term: gw
    date issued: 1988
    issuance: monographic
  language:
    language term: eng
  physical description:
    reformatting quality: preservation
    reformatting quality: access
    form: remote
    extent: 1 online resource (xi, 315 pages) : illustrations
  abstract: Network flow and matching are often treated separately in the literature and for each class a variety of different algorithms has been developed. These algorithms are usually classified as primal, dual, primal-dual etc. The question the author addresses in this work is that of the existence of a common combinatorial principle which might be inherent in all those apparently different approaches. It is shown that all common network flow and matching algorithms implicitly follow the so-called shortest augmenting path. This can be interpreted as a greedy-like decision rule where the optimal solution is built up through a sequence of local optimal solutions. The efficiency of this approach is realized by combining this myopic decision rule with an anticipant organization. The approach of this work is organized as follows. For several standard flow and matching problems the common solution procedures are first reviewed. It is then shown that they all reduce to a common basic principle, that is, they all perform the same computational steps if certain conditions are set properly and ties are broken according to a common rule. Recognizing this near-equivalence of all commonly used algorithms the question of the best method has to be modified - all methods are (only) different implementations of the same algorithm obtained by different views of the problem.
  table of contents: Contents: Preliminaries -- The Class of General Matching Problems -- Network Flow Algorithms Revisited -- Bipartite Matching Problems -- The 1-Matching Problem -- The b-Matching Problem -- References.
  note: Ulrich Derigs.
  note: Electronic resource.
  note: Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002. http://purl.oclc.org/DLF/benchrepro0212 MiAaHDL
  note: digitized 2010 HathiTrust Digital Library committed to preserve pda MiAaHDL
  note: Includes bibliographical references (pages [299]-315).
  subject:
    topic: Combinatorial optimization
  subject:
    topic: Network analysis (Planning)
  subject:
    topic: Matching theory
  subject:
    topic: Combinatorial optimization
  subject:
    topic: Matching theory
  subject:
    topic: Network analysis (Planning)
  classification: QA402.5 .D47 1988
  classification: Q500 .L427 v.300 1988
  classification: 511/.6
  classification: 83.03
  related item:
    title info:
      title: Programming in networks and graphs
    name:
      name part: Derigs, Ulrich, 1950-
    origin info:
      publisher: Berlin ; New York : Springer-Verlag, c1988
    identifier: (DLC) 88003163
    identifier: (OCoLC)17507567
  related item:
    title info:
      title: Lecture notes in economics and mathematical systems ; 300
  identifier: 9783642517136 (electronic bk.)
  identifier: 3642517137 (electronic bk.)
  identifier: 0387189696 (U.S. : pbk.)
  identifier: 9780387189697 (U.S. : pbk.)
  identifier: http://proxy.library.tamu.edu/login
  record info:
    record content source: OCLCE
    record creation date: 100326
    record change date: 20260420204146.1
    record identifier: in00003506615
    language of cataloging:
      language term: eng