Muutke küpsiste eelistusi

E-raamat: Network Flow Algorithms

4.00/5 (1 hinnangut Goodreads-ist)
(Cornell University, New York)
  • Formaat: EPUB+DRM
  • Ilmumisaeg: 05-Sep-2019
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781316946664
Teised raamatud teemal:
  • Formaat - EPUB+DRM
  • Hind: 45,68 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Network Flow AlgorithmsSuurem pilt
  • Formaat: EPUB+DRM
  • Ilmumisaeg: 05-Sep-2019
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781316946664
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Network flow theory has been used across a number of disciplines, including theoretical computer science, operations research, and discrete math, to model not only problems in the transportation of goods and information, but also a wide range of applications from image segmentation problems in computer vision to deciding when a baseball team has been eliminated from contention. This graduate text and reference presents a succinct, unified view of a wide variety of efficient combinatorial algorithms for network flow problems, including many results not found in other books. It covers maximum flows, minimum-cost flows, generalized flows, multicommodity flows, and global minimum cuts and also presents recent work on computing electrical flows along with recent applications of these flows to classical problems in network flow theory.

This comprehensive text and reference for graduate students and professionals in theoretical computer science, operations research, and discrete math offers an up-to-date, unified view of efficient combinatorial algorithms for a wide variety of network flow problems, including recent work on computing electrical flows and their applications.

Arvustused

'More than half a century since network flow theory was introduced by the 1962 book of L. R. Ford and D. R. Fulkerson, the area is still active and attractive. This book, based on course materials taught at Stanford and Cornell Universities, offers a concise and succinct description of most of the important topics, as well as covering recent developments. Its use in graduate courses related to algorithms and optimization is highly recommended.' Toshihide Ibaraki, Kyoto College of Graduate Studies for Informatics, Japan 'A succinct and very readable account of network flow algorithms covering the classics and the latest developments. The perfect book for a course on network flow algorithms and a reference for the state of the art. It will be a frequently used addition to my bookshelf.' Kurt Mehlhorn, Max-Planck-Institut für Informatik 'The book includes many lemmas and theorems with proofs. It provides a succinct, amalgamated view of a broad mixture of effective combinatorial algorithms for network flow problems, including many topics not found in other textbooks I strongly recommend the book for students and researchers.' S. V. Nagaraj, SIGACT News

Muu info

Offers an up-to-date, unified treatment of combinatorial algorithms to solve network flow problems for graduate students and professionals.
Preface ix
Acknowledgments xi
1 Preliminaries: Shortest Path Algorithms
1(22)
1.1 Nonnegative Costs: Dijkstra's Algorithm
2(4)
1.2 Negative Costs: The Bellman-Ford Algorithm
6(5)
1.3 Negative-Cost Cycle Detection
11(12)
Exercises
19(1)
Chapter Notes
20(3)
2 Maximum Flow Algorithms
23(57)
2.1 Optimality Conditions
26(7)
2.2 Application: Carpool Sharing
33(3)
2.3 Application: The Baseball Elimination Problem
36(5)
2.4 Application: Finding a Maximum Density Subgraph
41(5)
2.5 Most Improving Augmenting Paths
46(5)
2.6 A Capacity Scaling Algorithm
51(2)
2.7 Shortest Augmenting Paths
53(3)
2.8 The Push-Relabel Algorithm
56(24)
Exercises
69(7)
Chapter Notes
76(4)
3 Global Minimum Cut Algorithms
80(36)
3.1 The Hao-Orlin Algorithm
82(7)
3.2 The MA Ordering Algorithm
89(4)
3.3 The Random Contraction Algorithm
93(7)
3.4 The Gomory-Hu Tree
100(16)
Exercises
110(3)
Chapter Notes
113(3)
4 More Maximum Flow Algorithms
116(16)
4.1 Blocking Flows
116(4)
4.2 Blocking Flows in Unit Capacity Graphs
120(2)
4.3 The Goldberg-Rao Algorithm
122(10)
Exercises
128(2)
Chapter Notes
130(1)
Permissions
130(2)
5 Minimum-Cost Circulation Algorithms
132(56)
5.1 Optimality Conditions
135(5)
5.2 Wallacher's Algorithm
140(6)
5.3 Minimum-Mean Cycle Canceling
146(8)
5.4 A Capacity Scaling Algorithm
154(6)
5.5 Successive Approximation
160(7)
5.6 Network Simplex
167(3)
5.7 Application: Maximum Flow Over Time
170(18)
Exercises
176(8)
Chapter Notes
184(4)
6 Generalized Flow Algorithms
188(36)
6.1 Optimality Conditions
190(8)
6.2 A Wallacher-Style GAP-Canceling Algorithm
198(7)
6.3 Negative-Cost GAP Detection
205(4)
6.4 Lossy Graphs, Truemper's Algorithm, and Gain Scaling
209(9)
6.5 Error Scaling
218(6)
Exercises
221(2)
Chapter Notes
223(1)
7 Multicommodity Flow Algorithms
224(29)
7.1 Optimality Conditions
225(2)
7.2 The Two-Commodity Case
227(3)
7.3 Intermezzo: The Multiplicative Weights Algorithm
230(6)
7.4 The Garg-Konemann Algorithm
236(4)
7.5 The Awerbuch-Leighton Algorithm
240(13)
Exercises
249(2)
Chapter Notes
251(2)
8 Electrical Flow Algorithms
253(38)
8.1 Optimality Conditions
254(12)
8.2 Maximum Flow in Undirected Graphs
266(5)
8.3 Graph Sparsification
271(6)
8.4 A Simple Laplacian Solver
277(14)
Exercises
285(3)
Chapter Notes
288(2)
Permissions
290(1)
9 Open Questions
291(3)
References 294(13)
Author Index 307(3)
Index 310
David P. Williamson is a Professor at Cornell University, New York, in the School of Operations Research and Information Engineering. He has won several awards for his work in discrete optimization, including the 2000 Fulkerson Prize, sponsored by the American Mathematical Society and the Mathematical Programming Society. His previous book, The Design of Approximation Algorithms (Cambridge, 2011), co-authored with David B. Shmoys, won the 2013 INFORMS Lanchester Prize. He has served on several editor boards, and was editor-in-chief of the SIAM Journal on Discrete Mathematics. He is a Fellow of the ACM and of SIAM.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97813169466646e.html
Märksõnad: