√лавна€    Ex Libris     ниги    ∆урналы    —татьи    —ерии     аталог    Wanted    «агрузка    ’удЋит    —правка    ѕоиск по индексам    ѕоиск    ‘орум   
blank
blank
ѕоиск по указател€м

blank
blank
blank
 расота
blank
Garey M.R., Johnson D.S. Ч Computers and intractability. A guide to the theory of NP-completeness
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.


язык: en

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

—татус предметного указател€: √отов указатель с номерами страниц

ed2k: ed2k stats

√од издани€: 1979

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

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

ќперации: ѕоложить на полку | —копировать ссылку дл€ форума | —копировать ID
blank
ѕредметный указатель
#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
blank
–еклама
blank
blank
HR
@Mail.ru
       © Ёлектронна€ библиотека попечительского совета мехмата ћ√”, 2004-2017
Ёлектронна€ библиотека мехмата ћ√” | Valid HTML 4.01! | Valid CSS! ќ проекте