Index

W

walk of a tree, see tree walk

weak duality, 805

weight

of a cut, 1043 ex.

of an edge, 529

mean, 617 pr.

of a path, 580

weight-balanced tree, 301, 427 pr.

weighted bipartite matching, 497

weighted matroid, 394–398

weighted median, 194 pr.

weighted set-covering problem, 1050 pr.

weighted-union heuristic, 503

weighted vertex cover, 1040–1043

weight function

for a graph, 529

in a weighted matroid, 394

while, in pseudocode, 19

white-path theorem, 545

white vertex, 531, 540

widget, 1008

wire, 705, 988

WITNESS, 891

witness to the compositeness of a number, 890

worst-case running time, 26, 46