Network flow algorithms

by Williamson, David P.

Type Book

Rate 0.0 /5

Details

Files

Reviews

Download

Title Statements

Full title :Network flow algorithms / David P. Williamson, Cornell University.

Edition Statements

Publication Date:©2019 David P. Williamson

Publication Statements

Publisher(s):Cambridge University Press
Place of Publication:Cambridge, United Kingdom
Language:eng
Publication Date:©2019 David P. Williamson

The Physical Object

Description:xii, 314 pages : : illustrations ; : 24 cm

Edition Identifiers

ISBN:9781107185890, 1107185890, 9781316636831, 1316636836
oclc:on1089558077
LC Classification:T57.85
Dewey Decimal:003

1.Preliminaries: Shortest Path Algorithms -- 1.1.Nonnegative Costs: Dijkstra's Algorithm -- 1.2.Negative Costs: The Bellman-Ford Algorithm -- 1.3.Negative-Cost Cycle Detection -- Exercises -- Chapter Notes -- 2.Maximum Flow Algorithms -- 2.1.Optimality Conditions -- 2.2.Application: Carpool Sharing -- 2.3.Application: The Baseball Elimination Problem -- 2.4.Application: Finding a Maximum Density Subgraph -- 2.5.Most Improving Augmenting Paths -- 2.6.A Capacity Scaling Algorithm -- 2.7.Shortest Augmenting Paths -- 2.8.The Push-Relabel Algorithm -- Exercises -- Chapter Notes -- 3.Global Minimum Cut Algorithms -- 3.1.The Hao-Orlin Algorithm -- 3.2.The MA Ordering Algorithm -- 3.3.The Random Contraction Algorithm -- 3.4.The Gomory-Hu Tree -- Exercises -- Chapter Notes -- 4.More Maximum Flow Algorithms -- 4.1.Blocking Flows -- 4.2.Blocking Flows in Unit Capacity Graphs -- 4.3.The Goldberg-Rao Algorithm -- Exercises -- Chapter Notes -- Permissions -- 5.Minimum-Cost Circulation Algorithms -- 5.1.Optimality Conditions -- 5.2.Wallacher's Algorithm -- 5.3.Minimum-Mean Cycle Canceling -- 5.4.A Capacity Scaling Algorithm -- 5.5.Successive Approximation -- 5.6.Network Simplex -- 5.7.Applicatio…