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