Cook W.J., Cunningham W.H., Pulleyblank W.R. — Combinatorial optimization :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Cook W.J., Cunningham W.H., Pulleyblank W.R. — Combinatorial optimization

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

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

Название: Combinatorial optimization

Авторы: Cook W.J., Cunningham W.H., Pulleyblank W.R.

Аннотация:

A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics. One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade.

Язык:

Рубрика: Математика/

Серия: Сделано в холле

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

ed2k: ed2k stats

Издание: 1 edition

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

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

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

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

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

$deg_{G}(\cdot)$       166
$E_{=}$       146
$f_{x}$       38
$gap(\cdot)$       35
$G[\cdot]$ (induced subgraph)      10
$G\setminus \cdot$       10
$G^{x}$       166
$G_{=}$       146
$G_{b}$       189
$N(\cdot)$ (neighborset)      54
$o(\cdot)$       7
$oc(\cdot)$       130
$Z_{+}$       16
$\alpha$ -approximate cut      84
$\delta$ -path      247—249
$\delta(\cdot)$       12
$\gamma(.)$       12
$\kappa(\cdot)$       16
$\lceil\cdot\rceil$       7
$\lfloor\cdot\rfloor$       7
$\mathcal{P}$       309 313
$\mathcal{P}\mathcal{M}(G)$       201
$\mathcal{X}^{P}$ (characteristic vector)      87
$\nu(.)$ (matching number)      127
(b, u)-matching      182
(r, s)-cut      40
(r, s)-flow      38
(r, s)-paths      168
1-tree      253—255 260 261
1-tree bound      253—255 260 261
2-Factor      182 190 259 265 267
2-interchange      246 252
2-node cover      191
2-opt algorithm      246 247 251
2-optimal      246 247 252
3-opt algorithm      247 251
3-optimal      252
3-SAT      318 319
3-satisfiability problem      318
Accepts a word      322
Active node      63
Acyclic digraph      30 31 34 36 38
adjacent nodes      9
Admissible arcs      65
Affinely independent      211 212 218
Affinely-independent set      211 216
Affinely-independent vectors      216 218
Algorithm      313
All minimum cuts      84
Allowed sequence      313
Alphabet      311
Alternating path      128 134
Alternating tree      135 137 138 143 152
Arcs      19
Arcs, ends      19
Arcs, forward      19
Arcs, head      19
Arcs, incident      19
Arcs, parallel      19
Arcs, reverse      19
Arcs, tail      19
Arithmetic model      7 8
Artificial arc      107 111
Augmentation      115
Augmenting circuit      101—103 106 111
Augmenting Circuit Algorithm      102 103
Augmenting path      41 113 128 129 133 134 137 139 141—144
Augmenting path algorithm      42 129
Augmenting path theorem      128
Augmenting Path Theorem of Matchings      129 134
Auxiliary digraph      42 93 116
Average arc cost      103
B-factor      182 202
b-matching      186
b-matching algorithm      187
b-Matching Proximity Theorem      187 188
Bad node      163
Basic solution      331
Basis      88 331
Bidirected graphs      183
Binary search      312
Bipartite graph      47 48 53 59 60 92 99 118 127 128 130 131 133 134 136 137 145 163 181 182 188
Bipartite matching      47—49 53 59 136 137 143 145
Bipartite matching algorithm      137
Bipartite matching problem      99 118 128
Bipartition      47 92
Birkhoff's theorem      145 147 208
Bit model      7 8
Bit operations      6
Blossom      138
Blossom algorithm      138 140 186 201
Blossom Algorithm for weighted matching      154
Blossom inequality      148 209 217 239 265—268
Blossom separation      239 267
Boolean expression      316
Branch and bound      235 268
Branch and cut      235
Branching      288
Breadth-first search      33 42 44
Capacitated perfect b-matching      182
Capacitated transportation problem      92
Certificate      309 310 314
Certifies      302
Chained Lin — Kernighan      250 251 267 268
Change y      151
Change y at R      115
Characteristic vector      14
Cheapest Insertion      244
Chord      291
Chvatal rank      234
Circuit      10 282
Circuit flow      40
Circulation      55
CLIQUE      237
Closure of a digraph      49
Co-NP      315
Column generation      87 89 160 263
Comb inequality      264 265 267 268
commodities      86
Communications network      9 78
Complementary problem      315
Complementary slackness      17 163 164 180 181 330 331 334 335
Complementary slackness conditions      17 92 146 148 149 160 193 279 330 331
Complementary slackness theorem      92 331
Complete graph      9 155 157 170 172 179 191 241
Component      13
conformal      187
Conjunction      317
Connected component      263 267
Connected digraph      27 99 100 103 104 109
Connected forest      11
Connected graph      10—13 18 245
Connector problem      11
Conservation of flow      38
Contracting an edge      76 98
Contraction      122
Control zone      191 197
conv.hull      199
Convex combination      199 202 203 206 210 267
Convex hull      199—202 204
Cook's theorem      318
Core Lin — Kernighan Heuristic      248 252
Correct arc      22
Cover      48 127 130
Cramer's rule      220
Crossing sets      85
Cut (of a digraph)      40
Cut (of a graph)      12
Cut node      10
Cut-tree      81 85

Cutting planes      230 257 261—265 267—271
Cutting-plane algorithm      234
Cutting-plane proof      230
Cycling      89 108 109 111 112 333
def(G)      127
Deficiency      127
Degree of a node      166
Deleting nodes      10
demands      91
Derived graph      137
Derived pair      150
Dicircuit      19
Dicircuit, negative-cost      23—25 28 30 34
Dijkstra's algorithm      31—33 36 74 84 89 116 119
Dilworth's Theorem      61
DIMENSION      211—213 216 231 232
Dinits' algorithm      44
Dipath      19
Dipath, embedded      28
Dipath, length      44
Dipath, nonsimple      25
Directed Euler tour      99 100
Directed graph      19
Directed graph, arcs      19
Directed graph, loop      19
Directed graph, nodes      19
Directed graph, path      19
Directed graph, simple      19
Directed Hamiltonian circuit      320 321
Directed path      19
Directed path, cost of      20
Directed spanning tree      21 27
Disjoint perfect matchings      60
doubly linked list      70
Dual greedy algorithm      279 280
Dual linear-programming problem      17 26 88 94 112 122 145 148 155 162 165 260 262 328 330 331
Duality theorem      26 57 181 207 237 329 330
E(G) (edge set)      9
Edge connectivity      72
Edge cover      143
Edge scan      248
Edge-simple closed path      181
Edges      9
Edges, ends of      9
Edges, incident      9
Edges, parallel      9
Edmonds — Karp algorithm      44
Edmonds — Karp scaling algorithm      121
Edmonds' matching algorithm      239
Eliminated team      50
Ellipsoid method      325
Encoding numbers      311
Equality arc      113
Equality edges      146
Essential node      132
Euclidean distance      191
Euclidean matching problem      4 191
Euclidean traveling salesman problem      1 2 4 9 25
Euler tour      166 181 245
Even edge      194
Even node      135
Even set      168 182
Even spanning forest      194
Exact cover problem      319
Expanding pseudonodes      151 153
Exposed      127
Extendible subset      12
External face      96
Face      96 204
Facet      212—218 235
Facet-inducing inequality      212—218 235
Farkas' Lemma      89 200 201 327
Farkas' Lemma for Inequalities      326 329
Farthest Insertion      243 244 251
Feasible basis      331
Feasible flow      38
Feasible potential      21 22 25 26 28 32 33 36
Feasible preflow      63
Feasible solution      328 331
Finds and merges      15 18 141 142 158
Flow      38
Flow feasibility problem      53
Flow, amount      38
Flow, capacities      39
Flow, degenerate      108
Flow, excess      38
Flow, net      38
Flow, value      38
Flow-equivalent tree      81 85
Ford — Bellman algorithm      28—30 33 34 36
Ford — Fulkerson algorithm      42
Ford's Algorithm      22 24—28 30 34—36
Forest      11
Fourier — Motzkin elimination      326 327
FPM(G)      208
Fractional matching polytope      208
Fractional Matching Polytope Theorem      209
Frustrated tree      136—138 141 146
Full dimension      212—216
G(V,E) (graph)      9
G(x) (auxiliary digraph)      42 93
Gain sum      248
Gallai — Edmonds Partition      134 143 144 164
Gaussian elimination      326
Geometric matching problem      191
Global minimum cut      71
Goemans — Williamson Algorithm      195
Goldberg and Tarjan's algorithm      66
Goldberg's algorithm      66
Gomory — Chvatal cutting plane      230 231
Gomory — Hu algorithm      79 83
Gomory — Hu cut-tree      81 85
Good characterization      315
Gordan's Theorem      334
Graph      9
Graph connectivity      12
Greedy algorithm      273 274 277 284 290 293
Greedy principle      11
Hamiltonian circuit      241 252 309 310 314 320 321
Hamiltonian graph      314
Handle      264
Hao — Orlin algorithm      72
Held — Karp bound      255 256 258—261 264
Held — Karp Iterative Method      256 257
Heuristics      242
Hoffman — Kruskal Theorem      221
Hoffman's Circulation Theorem      55
Hopcroft — Karp Algorithm      143
Hungarian algorithm      146
Hyperplane      204
Hypomatchable      217
Incidence matrix      27 222
Incorrect arc      22
Incrementing path      41
Indegree      99
Independence system      277
Independent set      61 274
Independent set, common      287 297
Induced subgraph      10
Inessential node      132 144
Insertion methods      243
Integer linear programming      144
Integral flow      128 133
Integral polyhedron      219—221 224—226 235
Interior-point method      325
Internally node-disjoint path      62
Irrational capacities      43
k-opt algorithm      247
Karger's algorithm      76
Koenig's Theorem      48 61 130 134 143

1 2

О проекте