N

| < Day Day Up > |

# Index

### N

N (set of natural numbers), 1070
naive algorithm for string matching, 909- 911
NAIVE-STRING-MATCHER, 909
natural cubic spline, 767 pr.
natural numbers (N), 1070
negative of a matrix, 729
negative-weight cycle
and difference constraints, 603
and relaxation, 613 ex.
and shortest paths, 582
negative-weight edges, 582- 583
neighbor, 1083
neighborhood, 669 ex.
neighbor list, 683
nesting boxes, 615 pr.
net flow across a cut, 655
network
admissible, 681- 683
bitonic sorting, 712- 716
comparison, 704- 709
flow, see flow network
for merging, 716- 718
odd-even merging, 721 pr.
odd-even sorting, 721 pr.
permutation, 722 pr.
residual, 651- 653
sorting, 704- 724
transposition, 721 pr.
NEXT-TO-TOP, 949
NIL, 20
node, 1087
see also vertex
nonbasic variable, 782
nondeterministic polynomial time, 981 n.
see also NP
nonhamiltonian graph, 979
noninstance, 974 n.
noninvertible matrix, 730
nonnegativity constraint, 777, 779
nonoverlappable string pattern, 922 ex.
nonsaturating push, 672, 678
nonsingular matrix, 730
nontrivial power, 855 ex.
nontrivial square root of 1, modulo n, 878
no-path property, 587, 608- 609
normal equation, 764
norm of a vector, 730
NOT function (¬), 987
NOT gate, 987
NP (complexity class), 967, 981, 983 ex.
NPC (complexity class), 968, 986
NP-complete, 968, 986
NP-completeness, 966- 1021
of the circuit-satisfiability problem, 987- 994
of the clique problem, 1003- 1006
of determining whether a boolean formula is a tautology, 1002 ex.
of the formula-satisfiability problem, 996- 998
of the graph-coloring problem, 1019 pr.
of the half 3-CNF satisfiability problem, 1018 ex.
of the hamiltonian-cycle problem, 1008- 1012
of the hamiltonian-path problem, 1017 ex.
of the independent-set problem, 1018 pr.
of the integer linear-programming problem, 1017 ex.
of the longest-simple-cycle problem, 1017 ex.
proving, of a language, 995- 996
of scheduling with profits and deadlines, 1020 pr.
of the set-covering problem, 1038 ex.
of the set-partition problem, 1017 ex.
of the subgraph-isomorphism problem, 1017 ex.
of the subset-sum problem, 1013- 1017
of the 3-CNF-satisfiability problem, 998- 1002
of the traveling-salesman problem, 1012- 1013
of the vertex-cover problem, 1006- 1008
of the 0-1 integer-programming problem, 1017 ex.
NP-hard, 986
n-set, 1073
n-tuple, 1074
null event, 1100
null tree, 1089
null vector, 731
number-field sieve, 905
numerical stability, 725, 743, 769

| < Day Day Up > |