Index
Abstract transitive closure, 174–175, 216–220
Active vertex, 411
Acyclic graph. see Digraph; Directed acyclic graph (DAG)
Acyclic network, 313–321, 334–335
maxflow, 427–429
Adjacency-lists representation, 31–35
digraphs, 36–37, 153, 155, 179
edge connectivity, 115–116
find/remove edge, 40
flow networks, 379
performance, 33–35, 37–40, 145–146
removing vertices, 41
standard adjacency-lists DFS, 97, 161
transitive closure, 174
weighted graphs/networks, 37, 230, 235–238, 278
Adjacency-matrix representation, 25–30
digraphs, 36–37, 153, 154–155, 169–172, 176, 179
flow networks, 379
linear-time algorithm, 59
performance, 29–30, 37–40, 144–146
removing vertices, 41
standard adjacency-matrix DFS, 97, 161
weighted graphs/networks, 37, 230, 233–238, 278
Adjacent vertices, 9
ADT, graph. see Graph ADT
Airline route, 283
All-pairs shortest path, 281, 304–311
acyclic networks, 318–320
BFS, 127–129
negative weights, 356–360
path relaxation, 288–290
and transitive closure, 175, 328–329
Arbitrage, 348–349
Arbitrary weight, 229
Articulation point, 117–118
Assignment problem, 74, 476–477
A* algorithm, 325
Augmenting-path method, 382–407
cycle canceling, 451
longest augmenting path, 396
maximum-capacity, 394, 399–401, 405–406
network simplex algorithm, 460–461
performance, 393, 395–406, 434–436
and preflow-push, 411
random flow networks, 402–404
randomized, 402
shortest augmenting path, 393–394, 398–399, 405–407
stack-based, 400
Back edge, 99, 113–115, 161–165, 202–203
Back link, 99–100
Bellman-Ford algorithm, 350–356, 358–360, 447
BFS tree, 124–129
Binary DAG, 188–190
Binary decision diagram (BDD), 189
Binary tree, 188–190
Bioconnectivity, 117–119
Bipartite matching, 73–74, 433–436, 476, 482
Boolean matrix multiplication, 169–172, 176–177
Boruvka’s algorithm, 244, 263–267
Breadth-first search (BFS), 81–82, 121–130
and DFS, 127–134
forest, 125
fringe size, 137–138
Bridge, 113–117
Bridges of Königsberg problem, 62–64
Call, program, 5
st-cut, 385
vertex-capacity constraints, 426
change priority operation, 253
Circuit, 4
Circulation, flow network, 377–378, 429
augmenting-paths, 391
cycle canceling, 449
DFS, 96
network simplex algorithm, 466–467
weighted graphs, 233–236
see also Graph ADT
Colorability problem, 75
two-coloring, 110–111
Communications network, 367–369
Complement, 12
Complete graph, 12
Computer science, 365
Connection, 3
Connectivity, 11–12
bioconnectivity, 117–119
digraphs, 158
edge, 438–439
equivalence relations, 184
k-connected graph, 119
maxflow, 437–438
random, 141–144
simple connectivity, 72, 106–109
st-connectivity, 119
strong connectivity, 72, 156–158, 205
Construct operation, 262
Constraint, 186
convex/nonlinear, 483
edge, 474
flow, 443
negative, 446–447
reduced, 454–457
see also Performance; Weighted graph
Critical edge, 398–399
Cut, 241
mincut, 386–387
set, 385
vertex, 117–118
Cycle, 10–11
DFS, 105–106
MSTs, 240–244
negative, 279–280, 348–350, 446–454
odd, 110
property, 242–243
Cycle-canceling algorithm, 372, 447–452
see also Network simplex algorithm
DAG. see Directed acyclic graph (DAG)
de Bruijn graph, 53
Decrease key operation, 255, 268–269, 297
Degrees-of-separation graph, 53
Delauney triangulation, 274
Depth-first search (DFS), 81–82, 87–91
and BFS, 127–134
classes, 96
cycle detection, 105–106
digraphs, 160–168
fringe size, 137–138
PFS, 253
running time, 95–96
simple connectivity, 106–109
standard adjacency representations, 97, 161
strong components algorithms, 207–214
topological sorting, 193–195, 201–204
transitive closure, 177–179
tree links, 99–100
and Trémaux exploration, 87–90
two-colorability, 110–111
and union-find, 108–109
vertex search, 109–110
see also DFS tree
Destination vertex, 14
DAGs, 194
spanning forest, 110
bridges, 113–117
diagraphs, 161–162
Diameter, network, 304
Difference constraints, 332–336, 338, 347
adjacency-lists representation, 36–37, 153, 155, 179
adjacency-matrix representation, 36–37, 153, 154–155, 169–172, 176, 179
decomposing, 166
defined, 152
DFS in, 160–168
directed cycle detection, 162–166, 187
edge direction, 149–150
even cycles, 74
grid, 152
isomorphism, 150
map, 154
random, 220
and relations, 182–183
reverse, 154–155
running time, 221–222
single-source reachability, 166–167
strong components, 157–158, 205–214
strongly connected, 72, 156–158, 205
transitive closure, 169–180, 216–220
and undirected graphs, 153, 155–162, 165–167, 179–180
uniconnected, 224
weighted, 277–278
Dijkstra’s algorithm, 256, 293–302
acyclic networks, 320
all-pairs shortest paths, 305–307
Euclidean networks, 323–326
negative weights, 349, 354–360
and Prim’s algorithm, 294–296
Directed acyclic graph (DAG), 14, 150, 186–204
binary, 188–190
defined, 155
dominators, 223
longest path, 199
partial orders, 184–185
scheduling problem, 186–187
sink/source, 195–199
strong components, 157
topological sorting, 187, 191–199
transitive closure, 201–204
weighted, 313–321
Directed cycle, 14, 155, 162–165, 187
Directed graph. see Digraph; Directed acyclic graph (DAG)
Directed path, 72, 152, 155, 224
Distances matrix, 289, 306, 360
Distribution network, 444–445
Distribution problem, 368, 430, 444–445, 475
Dominator, 223
Down link, 99–100, 161–162, 202–204
Dummy edge, 447–451, 454–455, 472
Dummy vertex, 376–377
Dynamic reachability, 223
Edge, 7–10
back, 99, 113–115, 161–165, 202–203
backward/forward, 383–384
class, 379
connectivity, 438–439
costs, 474
critical, 398–399
directed, 14
down, 99–100, 161–162, 202–204
eligible, 412, 455–457, 462–468
flows, 375
incident, 9
marking vertices, 93
parallel, 8, 18, 27, 34, 47, 237, 278
pointers, 232, 235–237, 277–278, 432
random, 47
separation, 112
tree, 99, 113–115, 161–162, 202
uncapacitated, 380
Edge data type, 17, 37, 231–232, 379, 390
Edge-based preflow-push algorithm, 413–414
Edge-connected graph, 113, 117, 438–439
Edge-separable graph, 112
Edmonds, J., 393
Eligible edge, 412, 455–457, 462–468
Enumeration, graph, 150–151
Equal weights, 228–229
Equivalence class, 183
Equivalence relation, 183
Equivalent problems, 328
Erdos, P., 144
Euclidean graph, 10
flow networks, 402–404
MSTs, 274–276
neighbor graphs, 49
networks, 322–326
Euclidean heuristic, 324–326
Euler path, 62–68
directed, 224
mail carrier, 477–478
two-way Euler tour, 109
Excess, vertex, 411
Existence problem, 75–76
Fat interface, 39
Feasible flow, 410, 430–432, 444
Feasible spanning tree, 453–455
Feedback vertex set, 224
Fibonacci computation, 188, 268
PFS, 302
preflow-push, 416–420
topological sort, 197–199
Find edge operation, 40–41
Flow cost, 443
augmenting-flow method, 382–407
backward/forward edges, 383–384
capacities, 372, 375, 385, 426
cut problems, 369–370, 385–386
defined, 375
distribution problems, 368, 430, 444–445, 475
equilibrium, 376–377
inflow/outflow, 375–377
matching problems, 369, 433–436, 476, 482
maxflow-mincut theorem, 385–387
model, 373–374
network simplex algorithm, 372, 453–470, 479
preflow-push method, 410–423
random, 402–404
representations, 379
residual, 388–391, 412, 417, 446, 453
value, 375–377
see also Maxflow problem; Mincost flow problem; Net-work
Floyd’s algorithm, 176, 290, 304, 307–311
negative weights, 349–351, 354
Ford, L. R., 382
Ford-Fulkerson method. see Augmenting-path method
Forest, 12
BFS, 125
Boruvka’s algorithm, 264
DFS, 98–103, 109, 124–125, 161–162, 164, 194
Kruskal’s algorithm, 258
spanning, 109
Four-color theorem, 76
Prim’s algorithm, 251–256
priority queue, 393
Fulkerson, D. R., 382
Function call graph, 50–52
Gabow’s algorithm, 206, 211–214
Geometric algorithm, 275–276
Goldberg, A., 410
Graph, 3–73
applications, 4–5
complete, 12
connected, 11–12
de Bruijn, 53
defined, 7
degrees-of-separation, 53
directed/undirected, 14–15
edge-connected/edge-separable, 112–113, 117
Euclidean, 10
function call, 50–52
interval, 53
multigraph, 8
neighbor, 49
random, 47–48
simple, 8
static, 21–22
subgraph, 9
transaction, 49–50
see also Digraph; Directed acyclic graph (DAG); Undirected graph; Weighted graph
adjacency-lists representation, 31–35
adjacency-matrix representation, 25–30
all-pairs shortest paths, 304–305
connectivity interface, 21–22
constructor, 18
equivalence relations, 184
graph-search functions, 91–97
iterator, 18–20
show function, 20
symbol table, 50
vertex degrees, 38
weighted graphs, 230–239
see also Class
Graph search, 81–147
ADT functions, 91–97
algorithm analysis, 140–146
bioconnectivity, 117–119
generalized, 131–138
Hamilton tour, 60
maze exploration, 82–86
priority-first search, 251–256, 296–302, 323, 392–393
randomized, 136–138
separability, 112–117
see also Breadth-first search (BFS); Depth-first search (DFS)
Graph-processing problem, 70–79
degree of difficulty, 71, 77–79
existence, 75–76
intractable, 75
tractable, 72
Grid digraph, 152
Hamilton path, 59–62, 224, 339–340
Height function, 412–415
Highest-vertex preflow-push, 420
Hypertext, 4
Immediate dominator, 223
Incident edge, 9
Independent set problem, 75
Indexing function, 51
Induced subgraph, 9
Infeasible problem, 336
Inflow, 375–377
Inheritance, 39
Initial height function, 413
Integer weights, 379–380
Interface, graph ADT, 16–24, 39
Intersection, 82
Interval graph, 53
Irreflexive relation, 183
Isomorphic graphs, 10, 29, 77, 150
Item, 3
Jarnik’s algorithm, 256
Job scheduling, 4, 150, 186–187
negative cycles, 348–350
see also Topological sorting
Johnson, D., 268
Johnson’s algorithm, 360
k-connected graph, 119
k-neighbor graph, 49
Königsberg, bridges of, 62–64
Kosaraju’s algorithm, 206–208
Kruskal’s algorithm, 243–244, 258–263, 268
Kuratowski’s theorem, 73
Least common ancestor (LCA), 459–460
Length, path, 11
Linear programming (LP), 333, 342–343, 365
maxflow, 439–440
multicommodity flow, 483
network flow algorithms, 371–372
Linear quantity, 59
back, 99
DFS tree, 99–100
down, 99–100, 161–162, 202–204
Locality property, 48
Longest paths, 75, 199, 315–320
augmenting paths, 396
difference constraints, 334–335
and shortest path, 329–330
Mail carrier problem, 74, 224, 477–478
maximum, 482
minimum-distance point matching, 369
Mathematical programming, 343
Maxflow problem, 372, 375–378, 382–440
acyclic networks, 427–429
augmenting-path method, 382–407
bipartite matching, 433–436
capacity constraints, 426
connectivity, 437–438
feasible flow, 430–432
general networks, 425–426
linear programming, 439–440
and mincost flow problem, 425, 472–473
mincost maxflow, 443–447
preflow-push method, 410–423
running time, 434–436
spanning tree, 454–455
standard, 425–426
undirected networks, 429–430
Maxflow-mincut theorem, 385–387, 437
Maximal connected subgraph, 11–12
Maximum-capacity augmenting path, 394, 399–401, 405–406
Maximum-cardinality matching, 433, 482
Maze, 82–86
Merchandise distribution, 368, 430, 444–445, 475
Mincost flow problem, 372, 443–479
assignment problem, 476–477
cycle-canceling algorithm, 372, 447–452
edge costs, 474
eligible edges, 455–457
feasible flow, 444–445, 472–473
flow cost, 443
mail carrier, 477–478
and maxflow problem, 425, 472–473
mincost maxflow, 443–447
reductions, 472–479
running time, 451
single-source shortest paths, 472–473
transportation, 475–476
see also Network simplex algorithm
Mincut, 386–387
Minimum spanning tree (MST), 72, 227–276
Boruvka’s algorithm, 244, 263–267
cut and cycle properties, 240–244
defined, 228
equal weights, 228–229
Euclidean, 274–276
Kruskal’s algorithm, 243–244, 258–263, 268
Prim’s algorithm, 243, 247–256, 263, 269
representations, 237–239
weighted-graph ADTs, 230–239
Minimum-distance point matching, 369
Modular arithmetic, 183–184
Multicommodity flow, 482–483
Multigraph, 8
Multisource paths, 314–318
Negative cost, 446–447
Negative cycle, 279–280, 348–350, 446–454
Negative weight, 345–365
arbitrage, 348–349
Bellman-Ford algorithm, 350–356, 358
Dijkstra’s algorithm, 349, 354–360
Floyd’s algorithm, 349–351, 354
acyclic, 313–321, 334–335, 427–429
adjacency representations, 37
communications, 368–369
distribution, 444–445
reliability, 370
residual, 388–391, 412, 417, 446, 453
telephone, 370
undirected, 429–430
weighted diameter, 304
see also Flow network; Shortest path
Network simplex algorithm, 372, 453–470
assignment problem, 476–477
eligible edges, 455–457, 462–468
feasible spanning tree, 453–455
implementations, 466–469
initialization, 464
parent-link representation, 458–464
performance, 466–470
shortest paths, 472–473
simplex method, 479
vertex potentials, 454–456, 468
see also Mincost flow problem
Node, 8
Nonlinear cost, 483
NP-hard problem, 75, 77, 339–340
Online algorithm, 22
Operations research (OR), 343, 365
Optimization, 76
Outflow, 375–378
adjacency-lists representation, 34
networks, 278
random graphs, 47
weighted graphs, 237
Parent-link representation
BFS tree, 127
cycle detection, 165
DFS tree, 99–100
network simplex algorithm, 458–464
Partial order, 184–185
Passage, 82
mail carrier, 477–478
weight, 277
see also Longest path; Shortest path
Paths matrix, 289–290, 306, 360
abstraction, 42–43
adjacency-lists representation, 33–35, 37–40, 145–146
adjacency-matrix representation, 29–30, 37–40, 144–146
augmenting-path method, 393, 395–406, 434–436
cycle canceling, 452
dense/sparse graphs, 13
DFS forests, 103
Dijkstra’s algorithm, 297–300, 324–326
equivalent problems, 330–331
Kruskal’s algorithm, 260–262
MST algorithms, 268–273
network simplex algorithm, 466–470
preflow-push, 419–423
preprocessing time, 106–108, 127, 216–217, 221–222
random graphs, 54
shortest-paths algorithms, 363–365
static graphs, 42
transitive closure, 179–180, 221–222
union-find algorithm, 145
vector-of-edges, 37–38
worst-case, 43–44
see also Running time
Planarity problem, 73
Pointer, edge, 232, 235–237, 277–278, 432
Polynomial-time reduction, 439
Postorder numbering, 101, 162, 193
Potential function, 416–419, 454–456, 468
Precedence constraint, 186, 332
Preflow, 410–411
Preflow-push method, 410–423
edge-based, 413–414
highest-vertex, 420
performance, 419–423
vertex-based, 416
Preorder numbering, 98–99, 101, 162
Preprocessing
DFS, 106–108
transitive closure, 216–217, 221–222
Prim’s algorithm, 243, 247–256, 263
and Dijkstra’s algorithm, 294–296
running time, 269
augmenting-path method, 392–393
Dijkstra’s algorithm, 296–302
Kruskal’s algorithm, 261–263
multiway heap implementation, 272
Priority-first search (PFS), 323
augmenting-path method, 392–393
Prim’s algorithm, 251–256
Program structure, 5
Pushdown stack, 123
Radar tracking system, 369
Random flow network, 402–404
Reachability, 152, 158, 166–167
DAGs, 201–204
digraphs, 205
dynamic, 223
see also Transitive closure
Reduced cost, 454–457
difference constraints, 333–336, 338
equivalent problems, 328
flow networks, 367
implications, 341
job scheduling, 332–338
linear programming, 333, 342–343
mincost flow, 472–479
polynomial-time, 439
shortest paths, 328–343
transitive, 223
upper/lower bounds, 342
Reflexive relation, 183
Relation, 182–183
Remove edge operation, 34, 40–41
Remove the minimum operation, 251, 268–271
Renyi, A., 144
Residual network, 388–391, 453
mincost flow, 446
Reverse topological sorting, 193–195
Road map, 282–283
Running time, 141
augmenting-path method, 393, 405
Bellman-Ford algorithm, 354–356
Boruvka’s algorithm, 265
DFS, 95–96
digraphs, 221–222
Dijkstra’s algorithm, 296, 299, 311
Floyd’s algorithm, 309–311
Kruskal’s algorithm, 260–262
maxflow, 434–436
mincost flow, 451
MST algorithms, 269–270
NP-hard problems, 339
path search, 61
preflow-push, 416–419
Prim’s algorithm, 269
random graph connectivity, 144
shortest path algorithms, 301
strong components in digraphs, 205–206
transitive closure, 172–174, 177, 180, 221–222
weighted graphs, 235
see also Performance
Scheduling problem, 4, 150, 483
DAGs, 186–187
precedence-constrained, 332–338
see also Topological sorting
Search. see Graph search
Selection, 331
digraphs, 152
networks, 278
relations, 183
Sentinel weight, 235, 278, 287
Separability, 112–117
Separation vertex, 117–118
Set-inclusion DAG, 184
acyclic networks, 313–321
augmenting paths, 393–394, 398–399, 405–407
Bellman-Ford algorithm, 350–356, 358–360
BFS, 121–123
defined, 279
Dijkstra’s algorithm, 293–302, 305–307, 349, 354–360
Euclidean networks, 322–326
Floyd’s algorithm, 304, 307–311, 349–351, 354–356
and longest path, 329–330
multisource, 314–318
negative weights, 345–361
network simplex algorithm, 472–473
NP-hard problems, 339–340
reduction, 328–343
relaxation, 285–292
shortest paths tree (SPT), 279, 287–288, 294
source-sink, 281, 294, 322–326
see also All-pairs shortest path; Network; Single-source shortest path
Simple connectivity, 72, 106–109
Simple graph, 8
DFS, 106
networks, 279
Simplex method, 479
Single-source longest paths, 334–335
Single-source shortest paths, 72, 127, 281
acyclic networks, 314–315
Dijkstra’s algorithm, 293–294
and mincost flow problem, 472–473
negative weights, 350–354
reachability, 166–167
Sink, 154, 195–197, 281, 375–378
Software library, 485
Sollin, G., 267
Sorting, 331
Source vertex, 14, 154, 195–197, 281, 375–378
Source-sink shortest path, 281, 294, 322–326
feasible, 453–455
maxflow, 454–455
network simplex algorithm, 457–464
see also Minimum spanning tree
st-connectivity, 119
Stack-based augmenting-path method, 400, 402
STL list, 31–33
Strong components, 157–158, 205–214
transitive closure, 217–219
Strong connectivity, 72, 156–158, 205
Subgraph, 9
forbidden, 73
maximal connected, 11–12
Subset inclusion, 184
Supply lines problem, 370, 386–387
Symbol table
find edge, 41
graph-building function, 50–52
indexing function, 51
Symmetric relation, 183
Tarjan, R. E., 410
Tarjan’s algorithm, 73, 206, 210–213
Telephone network, 370
Topological sorting, 150, 187, 191–199
multisource shortest-paths, 314–318
relabeling/rearrangement, 191–192
reverse, 193–195
Total order, 185
Tour, 10
Hamilton, 59–62
mail carrier problem, 74
traveling salesperson problem, 76
Tractable problem, 72
Traffic flow, 369
Transaction, 5
Transaction graph, 49–50
Transitive closure, 72, 169–180
and all-pairs shortest paths, 175, 328–329
Boolean matrix multiplication, 169–172, 176–177
DAGs, 201–204
DFS-based, 177–179
performance, 172–174, 177, 179–180, 221–222
of a relation, 183
Warshall’s algorithm, 172–175
Transitive reduction, 223
Transitive relation, 183
Transportation problem, 368, 475–476
Traveling salesperson problem, 76
BFS, 124–129
binary, 188–190
and DAGs, 188–190
DFS, 90, 98–103, 113–117, 161–162
edge, 99, 113–115, 161–162, 202
preorder tree traversal, 101
shortest-path tree (SPT), 279, 287–288, 294
see also Minimum spanning tree (MST)
Tree link, 99–100
Trémaux exploration, 83–86, 87–90, 109
Two-coloring, 110–111
Uncapacitated edge, 381
and digraphs, 153, 155–162, 165–167, 179–180
networks, 429–430
reachability, 205
underlying, 15
Uniconnected digraph, 224
Union, 12
Boruvka’s algorithm, 264–265
and DFS, 108–109
Kruskal’s algorithm, 263
performance, 145
Vector, vertex-indexed, 37, 96
Vector-of-edges representation, 24, 37
Vertex, 7–10
active, 411
adjacent, 9
cut, 117–118
degree of, 9
destination, 14
disjoint, 11
dummy, 376–377
excess, 411
fringe, 253
height, 412–415
indegree/outdegree, 14
inflow/outflow, 375–378
marking, 92–93
ordered pair, 14
potentials, 416–419, 454–456, 468
printing, 19–20
removing, 41
search, 109–110
separation, 117–118
sink/source, 14, 154, 195–197, 281, 375–378
Vertex-based preflow-push algorithm, 416
V-vertex graph, 7
Warshall’s algorithm, 172–175, 289–290, 307–309
Weighted diameter, 304
adjacency-matrix representation, 37
ADTs, 230–239
arbitrary weights, 228
bipartite matching, 74
digraphs, 277–278
edge weights, 234–235
equal weights, 228–229
integer weights, 379–380
negative weights, 345–365
path weight, 277
see also Minimum spanning tree (MST); Shortest path
Whitney’s theorem, 119
World Wide Web, 4