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

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

blank
blank
blank
Красота
blank
Lawler E.L. — Combinatorial Optimization: Networks and Matroids
Lawler E.L. — Combinatorial Optimization: Networks and Matroids

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

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



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


Название: Combinatorial Optimization: Networks and Matroids

Автор: Lawler E.L.

Аннотация:

Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.


Язык: en

Рубрика: Математика/Алгебра/Комбинаторика/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Abadie, J.      178
Acyclic digraph      29
Acyclic networks      68 69
adjacency      21 22
Aigner, M.      353
Aircraft scheduling problem      139
Alternating tree      193
Amari, S.      179
Apell, P.      180
ARC      20
Arc covering problem      2
Assignment problem      2 129 170
Assignment problem, reduction to min-cost flow problem      186
Augmentation of capacity problem      156
Augmenting path theorem, bipartite matching      188
Augmenting path theorem, network flows      112
Augmenting path theorem, nonbipartite matching      226
Augmenting path, flow      109 135
Augmenting sequence, matroid intersection      305 309
Augmenting sequence, matroid parity      363 364
Balinski, M.L.      178 216 262
Basic feasible solution      41 42
Basic optimal solution      41
Basic variables      41
Basic variables, backward arc      109
Basic variables, bactracing routine, nonbipartite matching      237
Bellman — Ford algorithm      74
Bellman's equations      65
Bellman, R.E.      105
Berge, C.      58 177 226 262
Bidirected flows      223—225
Bipartite graph      23
Birkhoff — von Neumann theorem      189 222
Birkhoff, G.      297
Blattner, W.      107
Blossom, nonbipartite matching      229
Bock, F.C.      355
Borchardt. C.W.      27
Border graph      309
Boruvka, O.      298
Branch-and-bound      10—11
Bruno, J.      325 354
Bruter, C.P.      297
Busacker, R.G.      130 177 178
Camerini, P.      367
Camion, P.      162 180
Capacity constraints, elimination of      171
Capacity, arc flow      110
Capacity, cutset      112
Cardinality intersection algorithm, matroid      313
Cardinality matching algorithm, bipartite      195
Cardinality matching algorithm, nonbipartite      238
Cardinality matching problem, reduction to max-flow problem      185
Cardinality, set      17
Carre, B.A.      106
Caterer problem      133
Cheriton, D.      299
Chinese postman's algorithm      260—261
Chinese postman's problem      222 259—261
Choquet, G.      298
Christofides, N.      58
Chromatic number problem      8
Chu, Yoeng-jiin      355
Chvatal, V.      37 58
Circuit, matroid      269
Circulations      138—142
CLIQUE      25
Closed path      26
Cockayne, E.J.      299
Cocycle      3 1
Coefficient matrix      41
Coffman, E.G.      262
Cographic matroid      281
Combinatorial analysis      1
Common transversals      302
Complementary graph      25
Complete bipartite graph      25
Complete digraph      24
Complete graph      24
Component, graph      26
Connected graph      26
Constrained twenty questions problem      9
Contraction, graph      25
Convex bipartite graph      196
Convex combination      51
Convex polyhedron      51
Convex polytope      51
Cook, S.      12
Cost vector      41
Cost-to-time ratio cycle problem      94—97
Courant, R.      299
Crapo, H.H.      296
Crew selection problem      359
Critical path technique      165—169
Cunningham-Greene, R.A.      107
Currency conversion problem      134
Cutset      32 111 112
CYCLE      26
Dantzig, G.B.      43 58 89 106 107 161 179
Degeneracy, linear programming      47
Degree      24
Degree-constrained subgraph problem      217
Dennis, J.B.      180
Dependent set, matroid      269
Digraph      20
Dijkstra's method      70
Dijkstra, E.W.      105 299
Dilworth theorem      141
Dilworth, R.P.      179
Dinic, E.A.      178
Dirac, G.A.      178
Directed cocycle      32
Directed cycle      28
Directed path      28
Directed spanning tree      29 304 348—352
Dowling, T.A.      353
Dreyfus, S.E.      98 104 294 299
Duality, digraph      33—36
Duality, linear programming      53—57
Duality, matroid      280—283
Duality, matroid' intersection      3 15
Duality, nonbipartite matching      239—241
Dulmage, .A.L.      215
Dynamic programming      60
Edmonds, J.      117 131 157 158 177 215 217 222 229 241 243 262 263 271 276 297 320 322 336 338 353 354
Elias, P.      177
Endogenous flow      136
Equivalence relation      18
Euler graph      36
Euler path      36
Even, S.      262 354
Experimental design problem      278
Exposed node      182
Extreme point      51
Face      33
Feasible circulation problem      143
Feasible flow      109
Feasible solution, linear programming      41
Feinstein, A.      177
Fischer, M.J.      105
Flow augmenting path      109
Flow network synthesis algorithm      287
Floyd, R.W.      106
Ford, L.R.      105 177 181 215
Forest      27
Forward arc      109
Frank, H.      177
Fredman, M.L.      106
Frisch, I.      177
Fujii, M.      219 261
Fujisawa, T.      179
Fulkerson, D.R.      104 109 177 179 180 181 215 271 297 322 353
Gabow, H.      263
Gale optimality      277
Gale — Shapley matching problem      211
Gale, D.      207 211 212 216 277 297
Garey, M.R.      299
Geometric dual      33
Geometric interpretation, linear programming      48—57
Ghouila-Houri, A.      177
Gilbert, E.N.      299
Gilmore, P.C.      209 216
Gilmore-Gomory matching      207—210
Glicksberg, I.      215
Glover, F.      196 215
Gomory, R.E.      174 181 209 216 299
Gowen, P.J.      130 178
Graham, R.L.      262 299
Graph      20
Graphic matroid      268
Graphoid      283
Greedy algorithm      267 275—277
Greedy algorithm, matric matroid      279
Greedy algorithm, variations      283—285
Grinold, R.C.      179
Gross, O.      198 215
Guy, R.      12
Hadley, G      58
Hall, M., Jr.      215
Hall, P.      353
Hamilton cycle      37
Hamilton graph      37
Hanan, M.      299
Harary, R.      58 297
Heuristic methods      10—12
Hitchcock — Koopmans transportation problem      169 171
Hitchcock, F.L.      181
Hoffman, A.J.      140 161 779 180 214
Holzmann, C.A.      297
Homosexual marriage problem      220
Hopcroft, J.E.      2§ 2&
Hu, T.C.      12 104 174—176 177 178 181 287 299
Huffman, D.A.      2
Hungarian method, weighted bipartite matching      201 207
Hungarian tree, bipartite matching      193
Hungarian tree, nonbipartite matching      240
Hypergraph      361
Hyperplane      51
In-degree      24
incidence      21
Independent set, matroid      268
Integer linear programming      10 11
Integral circulation theorem      160
Integral flow theorem      113
Integrality theorem, bipartite matching      189
Integrality, flow      160—165
Intersection graph      37
Iri, M.      177 178 179 354
Jarvis, J.J.      178
Jewell, W.S.      130 178
Jezior, A.M.      178
Johnson, D.B.      104
Johnson, D.S.      299
Johnson, E.L.      263
Kajitani, V.      325 353
Kantorovitch, L.      181
Kariv, O.      262
Karp, R.M.      9 12 23 117 131 157 158 177 215 262 355
Kasami, T.      261
Kautz, W.H.      298
Kelley, J.E., Jr.      180
Kilter conditions      144
Kilter diagram      144
Kilter number      144
Kishi, G.      325 353
Klee, V.      60 73 191 298
Klein, M.      130 178 200 216
Knapsack problem      62
Knuth, D.E.      12
Koenig — Egervary theorem      190—231
Krogdahl, S.      310 311 327—331 352
Kruskal, J.B.      161 180 266 298
Kuhn, H.W.      181 216
Kundu, S.      317 353
Kurotowski graphs      33
Kwan, Mei-ko      222 259 263
Labeling procedure, nonbipartite matching      235
Lageweg, B.J.      354
Land, A.H.      104
Lawler, E.L.      107 108 3 352 353 367
Lehman, A.      354
Lexicography      18 19
Line graph      38
Linear independence      41
Linear programming      39—57
Liu, C.L.      12
Liu, Tseng-hong      355
Lockhart, S.      263
Longest path problem      9 62
Loop      20
Losses and gains, network with      134—138
Lower bounds, flow      138
Machine sequencing problem      9
Maffioli, F.      367
Markowitz, H.      178 214
Marriage problem      189
Marshall. J.      108
Matching matroid      271
Matching, defined      182
Matrix multiplication      83
Matroid defined      268
Matroid matching problem      359
Matroid of graph      268
Matroid parity problem, generalized      364—367
Matroid partitioning algorithm      320
Matroid partitioning problem      319—323 356
Matroid polyhedra      334—338
Matroid polyhedral intersection theorem      338
Matroid sum      318
Maurras, J.F.      178
Max cut problem      8
Max flow problem      143
Max-flow min-cut theorem      113
Max-flow min-cut theorem, generalized      121 140
Max-flow min-cut theorem, linear programming interpretation      123—125
Max-min matching, bipartite      183 197—199
Max-min matching, nonbipartite      241
Maximal flow algorithm      115
Maximal flow algorithm, efficiency      116—119
Maximal spanning tree algorithm      286
Maximal spanning tree problem      266 278
Mayeda      179
McNaughton, R.      106
Melzak, Z.A.      299
Mendelsohn — Dulmage theorem      191
Mendelsohn — Dulmage theorem, matroid generalization      3 17
Mendelsohn, N.S.      215
Menger, K.      121 122
Meyer, A.R.      705
Min cost flow algorithm      131
Min cost flow problem      143
Min cost flow problem, reduction to weighted matching problem      187
Min cut problem      2
Min flow-max cut theorem      141
Minty, G.      32 109 179 180 282 283
Monge      180
Moore, E.F.      105
Moore, J.M.      2
Multicommodity flows      173—176
Multicommodity flows, analysis problem      175
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте