Garey M.R., Johnson D.S. — Computers and intractability. A guide to the theory of NP-completeness :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Garey M.R., Johnson D.S. — Computers and intractability. A guide to the theory of NP-completeness

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Computers and intractability. A guide to the theory of NP-completeness

Авторы: Garey M.R., Johnson D.S.

Аннотация:

This book's introduction features a humorous story of a man with a line of people behind him, who explains to his boss, "I can't find an efficient algorithm, but neither can all these famous people." This man illustrates an important quality of a class of problems, namely, the NP-complete problems: if you can prove that a problem is in this class, then it has no known polynomial-time solution that is guaranteed to work in general. This quality implies that the problem is difficult to deal with in practice.

Язык:

Рубрика: Computer science/Вычислимость/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1979

Количество страниц: 338

Добавлена в каталог: 17.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Graph, bridge connected      210.
Graph, chordal      191 194—195 201 217 285—286.
Graph, circle      191 194—195.
Graph, circular arc      191 194—195.
Graph, claw-free      195.
Graph, comparability      191 194—195 197 285.
Graph, complement      54 191 285.
Graph, complete      See cliques
Graph, complete bipartite      194.
Graph, cubic      194 198—199 285—286.
Graph, degree-bounded      84—86 190—192 194- 199—200 203—204 210 212.
Graph, edge      193—195 197—199 285.
Graph, edge directed      192 199.
Graph, Eulerian      131.
Graph, Hamiltonian      75 193 199.
Graph, intersection      191 199 204 219 285.
Graph, interval      198 295.
Graph, k-connected      198.
Graph, line      See edge graph
Graph, mixed      212.
Graph, outerplanar      195 197.
Graph, path      199 285.
Graph, planar      86—90 190—192 194—197 199 204 210 212 217 285.
Graph, reducible      192.
Graph, threshold      205.
Graph, total      195.
Graph, transitively orientable      See comparability
Graph, uniconnected      197.
Greatest common divisor      250.
Group isomorphism      285.
Grundy numbering      76
Guessing stage (of a nondeterministic algorithm)      28.
Hackenbush      257.
Hamiltonian circuit      35—36 47 56—60 72 85 154—155 167 199.
HAMILTONIAN COMPLETION      198.
Hamiltonian graphs      75 193 199.
HAMILTONIAN PATH BETWEEN TWO VERTICES      60 200.
Hamiltonian paths      60 199—200.
HC      See HAMILTONIAN CIRCUIT.
hemisphere      246.
Hereditary property      195.
Heuristic algorithm      122.
HEX      173 254.
Histories (of databases)      234.
Hitting sets      64 222 255.
Hitting string      229.
Homomorphisms of grammars      268.
Homomorphisms of graphs      202—203.
HYPERGRAPH 2-COLORABILITY      221.
Ianov schemes      276—277.
Incompletely specified automata      266—267.
Incongruences      249.
Independent set      53—54 133—134 139 146—147 149 181 194.
Independent set of a graph      53 190—191 195.
Induced subgraph      195—197.
Inequivalence (of languages)      265 267—269.
Inequivalence (of programs and schemes)      275—277.
Inferred finite stale automaton      267.
Inferred regular expression      268.
Infiniteness (of a language)      265 270.
Information retrieval      226—235.
Input length      6 20—23.
Instance of a problem      4 18.
Instant Insanity      173 258.
Instantiation      264.
Instructions, different length      273—274
INTEGER DIVISIBILITY BY FOUR      26.
INTEGER EXPRESSION INEQUIVALENCE      166 253.
Integer programming      245.
Integration      252.
Intersection (of languages)      266—270.
Intersection graphs      191 199 204 219 285.
Intersection patterns      222.
Interval graph, completion      198.
Interval graph, restriction to      285.
Intractable problem      8—12 174 181—186.
Intree partial orders      79.
Intree partial orders, restriction to      239—240.
Isomorphism problems      193 202 207 233 285.
Isomorphism, polynomial time      160—161.
Job shop scheduling      242.
K-closure of a graph      204.
K-connected graphs      198.
Karp, R.M.      14 47 118—119.
Kayles      254.
Kernel of a graph      204.
Key (in a relational database)      232—233.
Knapsack problem      9 65 96 134—139 149 247.
Knuth, D.E.      119—120.
Kth LARGEST SUBSET      114—115 225.
Languages      19—20.
Languages, context sensitive      176 271.
Languages, context-free      268—270.
Languages, developmental      270—271.
Languages, formal      265—271.
Languages, inequivalence of      265 267—269.
Languages, infiniteness of      265—270.
Languages, intersection of      266 270.
Languages, membership in      270—271.
Languages, non-emptiness of      265—270.
Languages, NP-complete      3—4 13—14 37—38 118—119.
Languages, polynomially equivalent      37.
Languages, quasi-realtime      266—270.
Languages, recognition of      24—25 31.
Languages, regular      269.
Languages, universality of      267 269.
Latin squares      285.
Least common multiple      250.
length function      20 92—95.
Levin, L.A.      119.
Line graphs      See edge graphs
Linear arrangement, directed optimal      200.
Linear arrangement, minimum cut      201.
Linear arrangement, optimal      200.
Linear bounded automata      175—177 265.
LINEAR BOUNDED AUTOMATON ACCEPTANCE      265.
Linear codes      280.
Linear complementarity      288.
LINEAR DIVISIBILITY      159.
Linear equations      246.
Linear grammar      268—269.
Linear inequalities      245—246.
Linear programming      9 180 215—216
LINEAR SPACE ACCEPTANCE      175 265.
Literal      38.
Liveness (of Petri nets)      279.
Local replacement (proof by)      66—72.
Log-space complete foi P      179—180.
Log-space hard for P      180.
Log-space transformation      178—180.
Logarithmic space      177—181.
Logic circuits      283.
Logic problems      259—264
Longest circuit      213.
Longest common subsequence      228.
Longest common substring      228.
Longest path      75 213.
Loop programs      275—276.
Loop-free program schemes      278.
Lower bounds on complexity      181—182.
lp      See linear programming.
LR(K) grammars      268—269.
Many-one reducibility      113.
Matching in a graph      132 134 169 190 192.
Matching problems      192 202—203 221 224 256.
Matching techniques, use of      132 134 190 192—193 196 203 239.
Matching, 2-dimensional      78 221
Matching, 3-dimensional      46 50—53 221 224.
Matching, maximal      192.
Matching, maximum      192 202 256.

Matching, maximum subgraph      202.
Matching, minimum maximal      192.
Matching, minimum weight      132.
Matching, multiple choice      203.
Matching, numerical      224.
Matching, perfect      194.
Matching, set      221.
Mathematical programming      245—248.
Matrices      200—201 229—230
Matrix, augmentation      229.
Matrix, basis      246.
Matrix, covering      282.
Matrix, domination      281.
Matrix, partitioning      229.
Matrix, permanent of      169 252.
Matrix, sparse      229.
Matrix, totally unimodular      288.
Matroid intersection problem      208.
Matroid parity problem      287.
MAX CUT      210.
max function      92—95.
Maximal matchings      192.
Maximization problems      123.
Maximum 2-satisfiability      259.
MAXIMUM CLIQUE SIZE      164—165.
Maximum Cut      87.
Maximum likelihood ranking      281.
Maximum matchings      192
Maximum SATISFIABILITY      259—260.
Maximum weight branching      208.
Membership (in a language)      270—271
Metric dimension of a graph      204.
Metric, discrete Euclidean      207 209
Metric, Euclidean      209 212
Metric, rectilinear      209 219.
Microcode bit optimization      274.
Minimization problems      123.
MINIMUM CARDINALITY KEY      232.
Minimum cover      64 222.
Minimum cut      210.
Minimum cut linear arrangement      201.
Minimum disjunctive normal form      261.
Minimum equivalent digraph      65 79 198.
MINIMUM EQUIVALENT EXPRESSION      161—162 164.
MINIMUM EQUIVALENT EXPRESSION SIZE      164—165
MINIMUM MAXIMAL MATCHIN      192
Minimum spanning trees      130—131 206—209
Minimum sum of squares      75 225
MINIMUM TARDINESS SEQUENCE      73—74 236.
MINIMUM TEST COLLECTION      71—72 222.
Minimum weight matching      132.
Mixed graphs      212.
Modal logic      262.
Monadic recursion schemes      277.
MONOTONE 3SAT      259.
Morphisms      202—203.
Multi-commodity network flow      216—217.
Multicenter of a graph      219—220.
Multicoloring of a graph      144.
Multiple choice branchings      208.
Multiple choice knapsack problem      247.
Multiple choice matchings      203.
Multiple choice spanning trees      208.
Multiprocessor scheduling problems      65 106
NDTM      See nondeterministic Turing machine.
Nearest Neighbor algorithm      129—130.
Neseiril — Roedl dimension      203.
Network flow techniques, use of      210 215
Network flow with bundles      216.
Network flow with homologous arcs      215.
Network flow with lower bounds      216.
Network flow with multipliers      215.
Network flow, integral      215—217.
Network flow, minimum edge-cost      214.
Network flow, multi-commodity      216—217.
Network flow, path constrained      215.
Network flow, two-commodity      216—217.
Network reliability      211.
Network survivability      211.
NEXPTIME      183—184.
NLOGSPACE      180—181.
No wail flow shop      241—242.
Node cover      See VERTEX COVER
Non-emptiness (of a language)      265 270.
Nondeterministic algorithm      28—30.
Nondeterministic oracle Turing machine      161.
Nondeterministic Turing machine      12—13 30—31.
Normal form      78.
Normal form, Boyce — Codd      233.
Normal form, minimum disjunctive      261.
NOT-ALL-EQUAL 3SAT      259.
NP      13 27—34 181—186.
NP-compleie problem (or language)      3—4 13—14 37—38 118—119.
NP-complete in the strong sense      95—107 115
NP-easy      117
NP-equivalent      117—118 120.
NP-hard problem      109 113—117 163.
NP1      154—161
NPC      154 160—161.
NPSPACE      175—176.
NUMBER      90—95.
Number problems      94—95.
Number, achromatic      191.
Number, chromatic      191.
Number, composite      155—158 288.
Number, crossing      286.
Number, domatic      190.
Number, Grundy      76 203—204.
Number, prime      155—158
Number, threshold      205.
Number-theoretic problems      249 253.
Numerical matching      224.
Numerical partitioning problems      223—225.
ONE-IN-THREE 3SAT      259.
Open shop scheduling      241.
OPTIMAL LINEAR ARRANGEMENT      200.
Optimization problem      19 114 117 123 164—165.
Oracle luring machine      1 1 1—113
OTM      See oracle Turing machine
Outerplanar graphs      195 197.
Outtree partial orders      79.
Outtree partial orders, restriction to      239—240.
P      27 181—186.
p-center      219—220.
P-complete      119.
P-hard      119.
p-median      220.
P-reducibility      118.
Packing problems      124—127 221.
Parallel assignment instruction      273.
PARAMETER      4.
Parametric linear programming      245.
Parity problems      287.
Parsimonious transformation      169.
Partial orders      236—240
Partial orders, chain      236.
Partial orders, dimension of      287.
Partial orders, forest      239.
Partial orders, intree      79
Partial orders, outtree      79 239—240.
Partial orders, series-parallel      237.
Partition      47 90—95 223.
PARTITION INTO CLIQUES      193.
PARTITION INTO PATHS OF LENGTH TWO      76 193.
PARTITION INTO TRIANGLES      68—69 192—193.
Partitioning problems      191—194 209—210 221 223—225.
Partitioning, graph      191—194
Partitioning, matrix      229.
Partitioning, numerical      223—225.
Partitioning, set      221

1 2 3

О проекте