Index - Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

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