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

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

#P      168—170
#P-complete      168—170 208 211 214 225 252.
$\gamma$ -complete      159—160.
$\gamma$ -reducibility      158—159.
(3,1) graph      191
2-dimensional matching      78 221
2-matroid intersection      208 223
2-SATISF1ABILITY      49—50 78 259.
3-DlMENSlONAL MATCHING      46 50—53 72 78 221 224
3-matroid intersection      223.
3-PARTITiON      96—105 224
3-processor scheduling      239 287
3DM      See 3-DlMENSlONAL MATCHING.
3SAT (3-SATISFIABILITY)      46 66 259.
3SAT (3-SATISFIABILITY), MONOTONE      259.
3SAT (3-SATISFIABILITY), NOT-ALL-EQUAL      259.
3SAT (3-SATISFIABILITY), ONE-1N-THREE      259.
3SAT (3-SATISFIABILITY), PLANAR      259.
3SAT (3-SATISFIABILITY), QUANTIFIED      172 262.
Absolute performance ratio      128.
Acceptance (of a string)      24 31 265—266.
Achromatic number      191.
Acyclic directed graphs, restriction to      195 197 200 202—204 213 217.
Address expressions      273.
Algebraic equations      251.
Algorithm      4 25.
Algorithm, approximation      123—151.
Algorithm, exponential lime      6—11.
Algorithm, heuristic      122.
Algorithm, nondeterministic      28—30.
Algorithm, polynomial time      6—11 27.
Algorithm, pseudo-polynomial time      91—92 94—95 140—141.
And/or graphs      283.
Annihilation      256.
Approximation algorithms      123—151.
Approximation schemes      135—137 140—142.
Arrays      275.
Asymptotic performance ratio      128.
Automata      265—267 285.
Automata, finite state      265—267.
Automata, incompletely specified      266—267.
Automata, inferred      267.
Automata, linear bounded      175—177 265.
Automata, pushdown      266.
Automata, quasi-realtime      265—266.
Automata, slack      266.
Automata, state minimization for      266—267.
Automaton isomorphism      285.
Average case performance      149—151.
Axiom set minimization      263.
B-scheme      277.
Bandersnatch problem      1—4 121.
Bandwidth      200.
Basis matrix      246.
Best Fit algorithm      126—127.
Betweenness      279.
Biconnected graphs      210.
Bin packing      124—127 149 226.
Binary NP-compIete      120.
Binary testing      71—72
Bipartite graphs      194—196.
Bipartite graphs, restriction to      190—192 195—196 199—200 203 209 285—286.
Boolean expression      260—261.
Boolean formula      261—262.
Boolean function      261.
Bottleneck traveling salesman problem      212.
BOUNDED DEGREE SPANNING TREE      64 206.
Boyce — Codd normal form      233.
Branchings      208.
Bridge connected graphs      210.
Broadcast graphs      212.
Capacities in communication networks      206- 207 227.
Checkers      173.
Checking stage (of a nondeterministic algorithm)      28.
Chinese postman problem      212.
CHORDAI,GRAPH COMPLETION      201.
Chordal graphs      195 201 286.
Chordal graphs, restriction to      191 194—195 217 285.
Chromatic index      286.
Chromatic number      191.
Circle graphs, restriction to      191 194—195.
Circuit in a graph      35.
Circuit, logic      283.
Circuit, longest      213.
Circuit, shortest      213—214.
Circuit, simple      35
Circular arc graphs, restriction to      191 194—195.
Circular ones property      229—230 243.
Clause (in an instance of SATISFIABILITY)      38.
Claw-free graphs, restriction to      195.
CLIQUE      47 73 285.
CLIQUE COVER      See PARTITION INTO
CLIQUES, cliques      14 193—195.
Clustering      281.
Co-NP      156—157.
Co-NPC      157 160.
Cobham, A.      7 118.
Code Generation      272—274.
Coding iheory      280.
Colorability      191.
Combinatorial games      172—173
Combinatorial optimization problem      123
Communication networks      206—207
Comparability graphs      195 197.
Comparability graphs, restriction to      191 194—195 285.
Comparative containment      223.
Comparative divisibility      249.
Comparative inequalities      248.
Complement of a decision problem      29 114
Complement of a graph      54
Complete bipartite graphs      194.
Complete subgraphs      See cliques
Completeness, #P-      168—170.
Completeness, $\gamma$ -      159—160.
Completeness, binary NP-      120.
Completeness, EXPSPACE-      183.
Completeness, EXPTIME-      183.
Completeness, log space      179—180.
Completeness, NP-      3—4 13—14 118—119.
Completeness, P-      119—120.
Completeness, PSPACE-      170—177.
Completeness, sirong NP-      95—107 115 120.
Completion problems      198—199 210—211.
Component design (proof by)      72—74.
Composite numbers      155—158
Computer models      10—11 23—27.
Coniext-free grammars      268—270 285.
Conjunctive query      233 285.
Conjunctive satisfiability      263.
Connected subgraphs, restriction to      195—198.
connectivity problems      195—198 209—211.
Consecutive ones property      229—230.
Consecutive sets      230.
CONSTRAINED TRIANGULATION      218.
Containment (in programs and schemes)      277.
Context-sensitive grammars      271
Continuous knapsack problem      247.
Contraciability of a graph      202.
Cook — Karp class      119.
Cook's theorem      39—44.
Cook, S.A.      13—14 39 118.
Cook-reducibility      118.
Covering by cliques      194.
Covering by complete bipartite subgraphs      194.
Covering edge      79 190.
Covering matrix      282.
Covering minimum      64 222.
Covering problems      194 268.
Covering set      53 221—222.
Covering vertex      46 53—56 72 79 133—134 149 190.

Covering, exact      53 221.
Covering, Reynolds      268.
Crossing number of a graph      286.
Crossover      87—90.
Crossword puzzles      258.
Cubic graphs      198.
Cubic graphs, restriction to      194
CYCLE      See circuit
Cyclic ordering      279.
Cyclic scheduling      243.
D-morphism      203.
Daia compression      228—232.
data storage      226—228.
Database problems      232—235.
Deadlock avoidance      244.
Decision problem      13 18—19.
Decision problem, complement of      29 114 156—157.
Decision problem, subproblem of      80—90.
Decision tree      282.
DECODING OF LINEAR CODES      280.
Degree bounded graphs      196 206.
Degree bounded graphs, restriction to      84—86 199—200 203—204 210 212.
Degree sequence      201.
Deterministic Turing machine      23—27.
Developmental languages      270—271.
Diagonalizalion      184—185.
Diameter of a graph      205—206.
Different speed processors      238—240.
Dimension of a graph      204—205.
Dimension of a partial order      287.
Dimension, metric      204.
Dimension, Nesetril — Roedl      203.
Diophantine equations      245—247
Directed acyclic graph      See acyclic directed graph.
DIRECTED ELIMINATION ORDERING      201.
DIRECTED M-COMMODITY FLOW WITH LOWER BOUNDS      216.
Directed optimal linear arrangement      200.
DIRECTED TWO COMMODITY NETWORK FLOW      216.
Discrete Euclidean metric      207 209 212.
DISJOINT CONNECTING PATHS      217
Disjoint paths      217—218.
Disjunction, simply deviated      282.
Disjunctive normal form, minimum      261.
Divisibility      159 249—250.
DLOGSPACE      177—181.
Domatic number      190.
Dominating sets      75 190
Drum storage      227.
DTM      See deterministic Turing machine
Dynamic storage allocation      226
Edge coloring      286.
Edge cover      79 190.
Edge digraphs, restriction to      192 199.
Edge graphs      195 197.
Edge graphs, restriction to      193—195 198—199 285.
Edmonds, J.      7—8 13 118.
Encoding scheme      5 9—10 19—23 92—94.
Enforcer (in local replacement proofs)      69—72.
Ensemble computation      66—68 274.
Enumeration problem      167—170 214 225 285.
Equations, algebraic      251.
Equations, Diophantine      245—247 249—250.
Equations, linear      246.
Equations, quadratic Diophantine      250.
Equations, simultaneous      249
Equations, solvability of      250—251.
Equilibrium point      252.
ETOL grammar      270—271.
Euclidean metric      209
Euler tour      131
Eulerian graph      131.
EXACT COVER BY 3-SETS      53
Expected component sum      224—225.
Exponential expression      249.
Exponential time algorithm      6—11.
Expression, address      273.
Expression, Boolean      260—261.
Expression, exponential      249.
Expression, inferred regular      268.
Expression, integer      166 253.
Expression, minimum equivalent      161—162 164—165.
Expression, regular      76 174 267—268.
EXPSPACE      183—184.
EXPTIME      183—184.
Fault detection      283—284.
Feedback sets in graphs      75 85 191
File protection systems      235.
Finite function generation      280.
Finite memory programs      275.
Finite state automata      265—267.
FINITE STATE AUTOMATA INTERSECTION      266.
FINITE STATE AUTOMATON INEQUIVALENCE      265.
Finitely presented algebra      166 253 285.
First Fit algorithm      124—126.
First Fit Decreasing algorithm      126—127.
First order logic      262 264.
Flow problems      214—218.
Flow shop scheduling      241—242.
Foldability of conjunctive queries      233.
Forbidden pairs      203.
Foresis      104—106 193 195 202.
Forest partial orders      237 239—240.
Formal languages      265—271.
Formally recursive procedures      278.
Four color conjecture      84.
Freedom (in schemes and programs)      277—278.
Frequency tables for databases      235.
Fully polynomial time approximation scheme      135—137 140—141.
Function, boolean      261.
Function, finite      22 280.
Function, simple      276.
Function, space constructive      182.
Function, time constructive      182—183 185.
Games      172—173 254—258.
Gaussian elimination ordering      201 286.
Generalized games      173 254—258.
GENERALIZED HEX      173 254.
Generalized satisfiability      260.
Generic instance      18.
Generic transformation      39.
Genus of a graph      286.
Geography      173 254.
Geometric problems      209 212 219.
GF(2)      251.
Go      173 257.
Grammar homomorphism      268.
Grammar isomorphism      285.
Grammar, context-free      268—270 285.
Grammar, context-sensitive      271.
Grammar, ETOL      270—271.
Grammar, linear      268—269.
Grammar, LR(K)      268—269.
Grammar, programmed      270.
grammar, regular      269.
GRAPH 2-COLORABILITY      191.
GRAPH 3-COLORABILITY      76 191.
Graph coloring problems      76 84—90 133 141—145 149 191 286.
Graph completion problems      198—199 210-
Graph contraclability      202 331
Graph genus      286.
GRAPH GRUNDY NUMBERING      76 203—204.
Graph homeomorphism      202.
Graph homomorphism      202—203.
Graph isomorphism      155—158 180 285.
GRAPH K-COLORABILITY      181 191.
Graph partitioning      191—194 209—210.
Graph, acyclic directed      195 197 200 202—204 213 217.
Graph, and/or      283.
Graph, biconnected      210.
Graph, bipartite      190—192 194—196 199—200 203 209 285—286.

1 2 3

О проекте