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

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

Partitioning, variable      255.
PATH CONSTRAINED NETWORK FLOW      215.
Path distinguishes      204.
Path graph, completion      199.
Path graph, restriction to      285.
Path length, total      206.
Path problems      196 203—204 211 213—214
PATH SYSTEM ACCESSIBILITY      179.
Paths, disjoint      217—218.
Paths, Hamiltonian      60 199—200.
Paths, longest      75 79 213.
Paths, shortest      79 213—214.
Paths, simple      196.
Perfect matchings      194.
Performance guarantees      122—151.
Permanent of a matrix      169 252.
Permuiation generation      280.
PERT networks      218.
PET problems      119.
Petri net      279—280.
Ph      See polynomial hierarchy
Picture compression      232.
PLANAR 3SAT      259.
PLANAR GEOGRAPHY      254.
Planar graphs      195 197
Planar graphs, restriction to      86—90 194—196 199 204 210 217
PLANAR INDUCED SUBGRAPH      195.
PLANAR SUBGRAPH      197.
POLYLOGSPACE      180—181.
Polynomial complete problem      118.
Polynomial hierarchy      161—167 171.
Polynomial space completeness      170—177.
Polynomial time, algorithm      6—11 27.
Polynomial time, approximation scheme      135—137.
Polynomial time, DTM program      27.
Polynomial time, isomorphism      160—161.
Polynomial time, NDTM program      31.
Polynomial time, reduction      13.
Polynomial time, Turing reduction      111 113—117 158.
Polynomial time, verifiability      28 172.
Polynomial transformation      34—37 118 120.
Polynomially equivalent languages      37.
Polynomials      249—251.
Polynomialty related Length and Max functions      92—93.
Polytope non-adjacency      246—247.
Post Correspondence Problem      228.
Precedence constrained scheduling      81—83 142 144 149 287.
Predicate logic      263.
preemptive scheduling      236—237 240—242.
Prime attribute (in a relational database)      232—233.
Prime numbers      155—158 288.
Problem      4.
Processors, different speed      238—240.
Processors, identical      238—241.
Processors, uniform      See different speed.
Processors, unrelated      240.
Product polynomials      250—251.
Production planning      243.
Program schemes      275—278.
Programmed grammars      270.
Programming (mathematical)      245—248.
Programming (mathematical), integer      245.
Programming (mathematical), linear      9 155—158 180 215—216 287—288.
Programming (mathematical), parametric linear      245.
Programming (mathematical), quadratic      245.
Programming (mathematical), zero-one integer      245.
Programs, containment in      277.
Programs, DTM      23—26.
Programs, finite memory      275.
Programs, freedom in      277—278.
Programs, inequivalence of      275—277.
Programs, loop      275—276.
Programs, NDTM      30—32.
Programs, OTM      111—113.
Programs, strong inequivalence of      276—277.
Propositional logic      259—261.
Provability      262.
Pseudo-polynomial time algorithm      91—92 94—95 140—141 210 223 225—227 236—238 240 243 249—250 252 281.
Pseudo-polynomial transformation      101—106.
PSPACE      170—178 184.
PSPACE-complete (or hard) problems      254—258 265—271 275.
PSPACE-completeness      See polynomial
QBF      See QUANTIFIED BOOLEAN FORMULAS
Quadratic assignment problem      218.
QUADRATIC DIOPHANTINE EQUATIONS      250.
Quadratic programming      245.
QUANTIFIED 3SAT      172 262.
QUANTIFIED BOOLEAN FORMULAS      171—172 261—262.
Quasi-realtime automata      265—266.
Quasi-realtime languages      266 270.
Question      18.
Radius of a graph      205.
Ramsey theory      191.
Randomization tests      281.
Reachability      279.
Reasonable encoding scheme      9—10 20—23.
Recognition (of a language)      24—25 31.
Rectilinear metric      209 219.
Recurrence relations      251.
Recursive language      154.
Reducibility, $\gamma$ -      158—159.
Reducibility, Cook-      118.
Reducibility, Karp-      118.
Reducibility, many-one      118.
Reducibility, P-      118.
Reducibility, truth-table      164—165.
Reducibility, Turing      111—113 158.
Reducible graphs, restriction to      192.
Reduction of one problem to another      13—14 113—117.
Redwood furniture      257.
Register allocation      272—273.
REGISTER SUFFICIENCY      272.
REGULAR EXPRESSION NON-UNIVERSALITY      174 267.
Regular expressions      76 174 231 267—268.
Regular grammar      269.
Regular graph, restriction to      190 285.
Relational databases      232—235.
Relativization      184—186.
Resource constrained scheduling      239.
Restriction (proof by)      63—66.
Retrieval time      226—227.
Reynolds covering      268.
Routing problems      211—214.
Safety in databases      234.
Safety in file protection systems      235.
SAT      See SATISFIABILITY
Satisfiability      13 107 169 181 259.
SATISFIABILITY OF BOOLEAN EXPRESSIONS      161—162
Satisfiability problems      259—263
Satisfiability, conjunctive      263.
Satisfiability, generalized      260.
Satisfiability, maximum      259—260.
Satisfiability, modal logic      262.
Satisfying truth assignment      38—39.
Scheduling      See also sequencing.
Scheduling, 3-processor      239 287.
Scheduling, Bow shop      241—242.
Scheduling, cyclic      243.
Scheduling, job shop      242.
Scheduling, multiprocessor      65 96 106 238—241.
Scheduling, open shop      241.
Scheduling, precedence constrained      81—83 144 149 239 287.
Scheduling, preemptive      236—237
Scheduling, resource constrained      239
Schemes      276.

Schemes, B-      277.
Schemes, containment in      277.
Schemes, freedom in      277—278.
Schemes, Ianov      276—277.
Schemes, inequivalence of      276—277.
Schemes, loop-free program      278.
Schemes, program      275—278.
Schemes, wtrong inequivalence of      276—277.
Search problems      110—111 119 167.
Second order logic      264.
Semi-group isomorphism      285.
sequencing      70 73—74 96 236—238 71 96 102—103
Sequential truth assignment      254.
Series-parallel partial orders, restriction to      237.
Set basis      222.
Set covering      53
Set matching      221.
Set PACKING      75 221.
Set panitioning      221.
Set problems      221—225.
Set Splitting      76 221.
Shapley — Shubik voting power      280.
Shop scheduling      241—242.
Shortest circuit      213—214.
Shortest common supersequence      228.
Shortest common superstring      228.
Shortest paths      79 213—214.
Simple circuits      35 196.
Simple functions      276.
Simple paths      196.
Simultaneous equations      249 251.
Size of a problem instance      5—6.
Slack automata      266.
Solvability of equations      250—251.
Space complexity      170—181.
Space constructive function      182.
Spanning tree parity      287.
Spanning trees      130—132 168 206—209 287.
Spanning trees, $K^{th}$ best      208.
Spanning trees, bounded diameter      206.
Spanning trees, capacitated      206—207.
Spanning trees, degree constrained      206.
Spanning trees, directed      208.
Spanning trees, geometric      207 209.
Spanning trees, isomorphic      207.
Spanning trees, maximum leaf      206.
Spanning trees, multiple choice      208.
Spanning trees, optimum communication      207.
Spanning trees, shortest total path length      206.
Sparse matrices      229.
Stacker-crane problem      212—213.
Stale minimization for finite automata      266—267.
Strong NP-compIeteness      See NP-complete in the strong sense
Structured string      21—22.
SUBFOREST ISOMORPHISM      105—106 202.
Subgraph homeomorphism      285.
Subgraph Isomorphism      18 20 64 104 202.
Subgraph problems      75 193—198
Subgraph with property      11 195.
Subgraph, balanced complete bipartite      196.
Subgraph, bipartite      196.
Subgraph, chordal      195.
Subgraph, clique      194—195.
Subgraph, comparability      195.
Subgraph, complete      See clique.
Subgraph, connected      195—198.
Subgraph, cubic      198.
Subgraph, degree-bounded      196.
Subgraph, edge      197.
Subgraph, forest      105—106 195 202.
Subgraph, independent      194—195.
Subgraph, induced      195—197.
Subgraph, isomorphic      193 202.
Subgraph, minimum k-connected      198.
Subgraph, outerplanar      195.
Subgraph, planar      197.
Subgraph, transitive      197.
Subgraph, uniconnected      197.
Subproblem of a decision problem      80—90.
Subsequences      228.
SUBSET PRODUCT      224.
SUBSET SUM      223.
substrings      228—229 231—232.
Subsumption      264.
Supergraph problems      198—199.
Supersequences      228.
Superstrings      228.
Tardiness      73—74 236—237
Tautology      261.
Testing problems      71—72
Thickness of a graph      286.
Threshold number of a graph      205.
Tiling      12
Time complexity      6 26
Time constructive function      182—183 185.
Timetables      243.
Total graphs, restriction to      195.
Total path length      206.
Total unimodularity      288.
Tournaments, restriction to      213.
Transformation      See polynomial transformation
Transitive digraph      197.
Transitive reduction      79 198.
Transitively orientable graphs      See comparability graphs.
Traveling salesman      18—20 27—29 35—36 95—96 117 211—212.
TRAVELING SALESMAN EXTENSION      116—117.
Traveling salesman problem      4—6 115—117 123 128—132 139 147
Tree transducers      271.
Trees, restriction to      104 190 198 202 210.
Triangle free graphs, restriction to      193 195—196.
Triangle inequality      128—129.
Triangulation      218 288.
Tries      226.
Truth assignment      38 261.
Truth functionally complete connectives      261
Truth-table reducibility      164—165.
TSE      See TRAVELING SALESMAN EXTENSION
Turing machine, deterministic      23—27.
Turing machine, nondeterministic      12—13 30—31.
Turing machine, nondeterministic oracle      161.
Turing machine, oracle      111—113 184—185.
Turing reduction      See polynomial time turing reduction
Turing, A.      12.
Two-commodity network flow      216—217.
Unary NP-complete      120.
Unconnected graphs      197.
Undecidable problems      12 245 257 264 269.
UNDIRECTED FLOW WITH LOWER BOUNDS      216.
Unification      252—253 264.
Uniform processors      See different speed processors.
UNIT RESOLUTION      179.
Universality (of a language)      267 269.
Unrelated processors      240.
Variable partition truth assignment      255.
VC      See VERTEX COVER
Vector addition systems      279—280.
Vector problems      224—225 248 279—280.
Vertex cover      46 53—56 72 79 85 133—134 149 190.
Vertex elimination ordering      201.
Vertex ordering problems      199—201.
Vertex substitute      85—86.
Voting power      280.
Weighted completion time      237 240—241.
X3C      See EXACT COVER BY 3-SETS.
Yes-instance      18.
Zero-one integer programming      245.

1 2 3

О проекте