Algorithmic Aspects of Flows in Networks - Günther Ruhe

Algorithmic Aspects of Flows in Networks

(Autor)

Buch | Softcover
203 Seiten
2012 | Softcover reprint of the original 1st ed. 1991
Springer (Verlag)
978-94-010-5523-9 (ISBN)
53,49 inkl. MwSt
fEt moi, ...sifavait sucommenten rcvenir, One service mathematics has rendered the jen'yseraispointall,,: human race. It hasput rommon senseback JulesVerne whereit belongs, on the topmost shelf next tothedustycanisterlabelled'discardednon- Theseriesis divergent; thereforewemaybe sense'. ahletodosomethingwithit. EricT. Bell O. Heaviside Mathematicsisatoolforthought. Ahighlynecessarytoolinaworldwherebothfeedbackandnon- linearitiesabound. Similarly, allkindsofpartsofmathematicsserveastoolsforotherpartsandfor othersciences. Applyinga simplerewritingrule to thequoteon theright aboveonefinds suchstatementsas: 'One service topology hasrenderedmathematicalphysics ...'; 'Oneservicelogichasrenderedcom- puterscience ...';'Oneservicecategorytheoryhasrenderedmathematics ...'. Allarguablytrue. And allstatementsobtainablethiswayformpartoftheraisond'etreofthisseries. This series, Mathematics and Its Applications, started in 1977. Now that over one hundred volumeshaveappeareditseemsopportunetoreexamineitsscope. AtthetimeIwrote "Growing specialization and diversification have brought a host of monographs and textbooks on increasingly specialized topics.
However, the 'tree' of knowledge of mathematics and related fields does not grow only by puttingforth new branches. It also happens, quiteoften in fact, that branches which were thought to becompletely disparatearesuddenly seento berelated. Further, thekindandlevelofsophistication of mathematics applied in various sciences has changed drastically in recent years: measure theory is used (non-trivially)in regionaland theoretical economics; algebraic geometryinteractswithphysics; theMinkowskylemma,codingtheoryandthestructure of water meet one another in packing and covering theory; quantum fields, crystal defectsand mathematicalprogrammingprofit from homotopy theory; Liealgebras are relevanttofiltering; andpredictionandelectricalengineeringcanuseSteinspaces. And in addition to this there are such new emerging subdisciplines as 'experimental mathematics','CFD', 'completelyintegrablesystems','chaos, synergeticsandlarge-scale order', whicharealmostimpossibletofitintotheexistingclassificationschemes. They drawuponwidelydifferentsectionsofmathematics. " By andlarge, all this stillapplies today.
Itis still truethatatfirst sightmathematicsseemsrather fragmented and that to find, see, and exploit the deeper underlying interrelations more effort is neededandsoarebooks thatcanhelp mathematiciansand scientistsdoso. Accordingly MIA will continuetotry tomakesuchbooksavailable. If anything, the description I gave in 1977 is now an understatement.

§ 1 Foundations.- 1.1. General preliminaries.- 1.2. Graph theory.- 1.3. Algorithms and complexity.- §2 Maximum Flows.- 2.1. Problem statement and fundamental results.- 2.2. Augmenting paths and blocking flows.- 2.3. Scaling.- 2.4. Preflows and the Goldberg algorithm.- 2.5. Computational results.- 2.6. Characterization of all optimal solutions.- 2.7. Maximal flows between all pairs of vertices.- §3 Minimum-Cost Flow Problems.- 3.1. Problem statement and fundamental results.- 3.2. History of polynomial algorithms.- 3.3. The network simplex method.- 3.4. Computational results.- §4 Generalized Networks.- 4.1. Maximum flows in generalized networks.- 4.2. A combinatorial algorithm for the generalized circulation problem.- 4.3. The simplex method for minimum-cost generalized flows.- 4.4. Computational results.- § 5 Multicriteria Flows.- 5.1. Fundamental results.- 5.2. Complexity results.- 5.3. Algorithms.- 5.4. An exact method for bicriteria minimum-cost flows.- 5.5. Approximative methods for bicriteria flows.- 5.6. ?-optimality.- 5.7. Computational results.- 5.8. An application: Optimal computer realization of linear algorithms.- §6 Parametric Flows.- 6.1. Motivation and fundamental results.- 6.2. The number of breakpoints for parametric flow problems.- 6.3. Vertical algorithm for the parametric maximum flow problem.- 6.4. Horizontal algorithm for parametric optimal flows in generalized networks.- 6.5. Dual reoptimization for parametric changes in the minimumcost flow problem.- 6.6. Fuzzy network flows.- §7 Detecting Network Structure.- 7.1. Embedded networks, graph realization, and total unimodularity.- 7.2. Complexity results.- 7.3. Graph realization by means of m-hierarchies.- 7.4. Equivalent problem formulations using network flows.- 7.5. Numerical investigationsto determine embedded networks.- §8 Solution of Network Flow Problems With Additional Constraints.- 8.1. Introduction.- 8.2. A primal partitioning algorithm.- 8.3. Solution of a class of interval scheduling problems.- List of Algorithms.- List of Problems.- References.

Reihe/Serie Mathematics and Its Applications ; 69
Mathematics and Its Applications ; 69
Zusatzinfo VIII, 203 p.
Verlagsort Dordrecht
Sprache englisch
Maße 155 x 235 mm
Themenwelt Informatik Theorie / Studium Algorithmen
Mathematik / Informatik Mathematik Analysis
Mathematik / Informatik Mathematik Wahrscheinlichkeit / Kombinatorik
Wirtschaft Betriebswirtschaft / Management Unternehmensführung / Management
ISBN-10 94-010-5523-8 / 9401055238
ISBN-13 978-94-010-5523-9 / 9789401055239
Zustand Neuware
Haben Sie eine Frage zum Produkt?
Mehr entdecken
aus dem Bereich
IT zum Anfassen für alle von 9 bis 99 – vom Navi bis Social Media

von Jens Gallenbacher

Buch | Softcover (2021)
Springer (Verlag)
29,99
Interlingua zur Gewährleistung semantischer Interoperabilität in der …

von Josef Ingenerf; Cora Drenkhahn

Buch | Softcover (2023)
Springer Fachmedien (Verlag)
32,99