G

| < Day Day Up > |

# Index

### G

Gabow's scaling algorithm for single-source shortest paths, 615 pr.
gap character, 910 ex., 923 ex.
gap heuristic, 691 ex.
garbage collection, 127, 210
gate, 987
Gaussian elimination, 747
gcd, 852- 853, 856 ex.
see also greatest common divisor
general number-field sieve, 905
generating function, 86 pr.
generator
of a subgroup, 867
of , 877
GENERIC-MST, 563
GENERIC-PUSH-RELABEL, 674
generic push-relabel algorithm, 673- 681
geometric distribution, 1112
and balls and bins, 109
geometric series, 1060
gift wrapping, 955
global variable, 19
Goldberg's algorithm, see push-relabel algorithm
golden ratio (φ), 56, 86 pr.
good guy, 539 ex.
gossiping, 429
GRAFT, 519 pr.
Graham's scan, 949- 955
GRAHAM-SCAN, 949
graph, 1080- 1084
adjacency-list representation of, 528
adjacency-matrix representation of, 529
algorithms for, 525- 698
breadth-first search of, 531- 539
complement of, 1007
component, 554
constraint, 603- 605
dense, 527
depth-first search of, 540- 549
dynamic, 499 n.
∈-dense, 641 pr.
hamiltonian, 979
incidence matrix of, 403 pr., 531 ex.
interval, 379 ex.
nonhamiltonian, 979
shortest path in, 535
singly connected, 549 ex.
sparse, 527
static, 499 n.
tour of, 1012
weighted, 529
see also directed acyclic graph, directed graph, flow network, undirected graph, tree
graph-coloring problem, 1019 pr.
graphic matroid, 393, 579
GRAPH-ISOMORPHISM, 982 ex.
gray vertex, 531, 540
greatest common divisor (gcd), 852- 853
binary gcd algorithm for, 902 pr.
Euclid's algorithm for, 856- 862
with more than two arguments, 861 ex.
recursion theorem for, 857
greedoid, 404
GREEDY, 396
GREEDY-ACTIVITY-SELECTOR, 378
greedy algorithm, 370- 404
for activity selection, 371- 379
for coin changing, 402 pr.
compared to dynamic programming, 341, 350 ex., 373- 375, 380, 382- 383
Dijkstra's algorithm, 595- 601
elements of, 379- 384
for fractional knapsack problem, 382
greedy-choice property in, 380- 381
for Huffman code, 385- 393
Kruskal's algorithm, 568- 570
and matroids, 393- 399
for minimum spanning tree, 561
optimal substructure in, 381- 382
Prim's algorithm, 570- 573
for the set-covering problem, 1033- 1038
for task scheduling, 399- 402, 402 pr., 404 pr.
on a weighted matroid, 395- 398
for the weighted set-covering problem, 1050 pr.
greedy-choice property, 380- 381
of Huffman codes, 388- 390
of a weighted matroid, 396- 397
GREEDY-SET-COVER, 1035
grid, 692 pr.
group, 862- 869
cyclic, 877

| < Day Day Up > |