Network Flows: Theory, Algorithms, and ApplicationsA comprehensive introduction to network flows that brings together the classic and the contemporary aspects of the field, and provides an integrative view of theory, algorithms, and applications.
|
From inside the book
Results 1-3 of 73
Page 187
... example , if U = 2 " , the bound is exponential in the number of nodes . Moreover , the algorithm can indeed perform this many iterations , as the example given in Figure 6.18 illustrates . For this example , the algorithm can select ...
... example , if U = 2 " , the bound is exponential in the number of nodes . Moreover , the algorithm can indeed perform this many iterations , as the example given in Figure 6.18 illustrates . For this example , the algorithm can select ...
Page 410
... example of a tree . We associate three indices with each node i in the tree : a predecessor index , pred ( i ) , a depth index depth ( i ) , and a thread index , thread ( i ) . 5 2 7 3 i 123456789 325566 pred ( i ) 0 1 2 3 012 3 2 5 5 6 ...
... example of a tree . We associate three indices with each node i in the tree : a predecessor index , pred ( i ) , a depth index depth ( i ) , and a thread index , thread ( i ) . 5 2 7 3 i 123456789 325566 pred ( i ) 0 1 2 3 012 3 2 5 5 6 ...
Page 776
... example . For example , node 18 is in position 8 , so its predecessor is in position [ ( 8 – 1 ) / 3 ] 3 and its successors are in positions 3 ( 8 ) 3 + 2 = 23 to 3 ( 8 ) + 1 = 25. This property implies that if we maintain the array ...
... example . For example , node 18 is in position 8 , so its predecessor is in position [ ( 8 – 1 ) / 3 ] 3 and its successors are in positions 3 ( 8 ) 3 + 2 = 23 to 3 ( 8 ) + 1 = 25. This property implies that if we maintain the array ...
Contents
INTRODUCTION | 1 |
PATHS TREES AND CYCLES | 23 |
ALGORITHM DESIGN AND ANALYSIS | 53 |
Copyright | |
31 other sections not shown
Other editions - View all
Common terms and phrases
adjacency list Application arc costs arc flows arc lengths augmenting path augmenting path algorithm bipartite capacity scaling algorithm commodity constraints cost flow problem define denote Dijkstra's algorithm directed path discussion distance label example Exercise feasible flow feasible solution Fibonacci heap flow algorithms formulation implementation integer iteration label-correcting algorithm Lagrangian multiplier Lagrangian relaxation Lemma linear programming lower bound matching matrix maximum flow problem minimum cost flow minimum spanning tree multicommodity flow problem N₁ negative cycle network contains network flow problem network G network simplex algorithm node potentials nonnegative NP-complete O(nm objective function value operation optimal solution optimality conditions path from node polynomial preflow-push algorithm reduced cost residual network s-t cut satisfies scaling phase Section shortest path distances shortest path problem Show shown in Figure simplex method source node Suppose Theorem undirected units of flow upper bound variables zero