Авторизация
Поиск по указателям
Nishizeki T., Chiba N. — Planar Graphs: Theory and Algorithms (North-Holland Mathematics Studies)
Обсудите книгу на научном форуме Нашли опечатку?
Название: Planar Graphs: Theory and Algorithms (North-Holland Mathematics Studies)Авторы: Nishizeki T., Chiba N. Аннотация: Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.
Язык: Рубрика: Математика /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Издание: 1st editionГод издания: 1988Количество страниц: 232Добавлена в каталог: 15.11.2009Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
2 11 12 17 23 2 11 12 17 23 6 6 2-connected 5 3-connected 5 8 11 65 71 75 4-connected 172 5-colorable 85 Ab-critical path 113 Absolute worst-case ratio 121 Adjacency, list 28 34 Adjacency, matrix 27 Adjacent 3 Albertson, M.O. 122 ALCOLOR 104 Algorithm 23 Algorithm, approximation 119 122 163 164 166 170 Algorithm, deterministic 25 Algorithm, nondeterministic 25 Algorithm, polynomial time 25 119 ALRECOLOR 106 Alternating path 101 Ancestor 34 Andersen, L.D. 100 APATH 114 Appel, K. 84 Approximation algorithm 119 122 163 164 166 170 Arboricity 137 138 Array 27 Array, 1-dimensional 27 Array, 2-dimensional 27 Asano, T. 171 184 Asymptotic behavior 24 Asymptotic worst-case ratio 121 Back edge 30 35 37 Backtracking 144 Baker, B.S. 122 134 Bar-Yehuda, R. 140 Barycentric mapping 65 Basis 2 17 18 Basis, cycle 17 Batch processing algorithm 87 Berge, C. 20 Big-oh (O) 25 Bipartite graph 6 10 164 Block 5 Blocking edge 216 BOND 71 Bond, triple 71 Booth, K.S. 33 42 48 Bound for planar graph 19 Boundary 7 193 209 Breadth-first search (BFS) 31 BREADTH-FIRST-SEARCH 31 Bridge 5 8 Bubble up 54 Bush form 40 41 49 C-node 41 C4 143 Capacity 186 Capacity, rule 186 Cederbaum, I. 33 Chiba, N. 33 65 87 122 137 141 144 171 Chromatic, index 99 Chromatic, k 84 Chromatic, number 83 Class P 25 Class-P 25 CLIQUE 137 138 Clique, maximal 137 138 144 147 Closed path 4 COLOR 102 Coloring 83 Coloring, edge 99 Coloring, k 83 101 Coloring, problem 26 83 Coloring, vertex 83 Combinatorial dual 16 17 18 Combinatorial explosion 25 Complete, bipartite graph 1 6 Complete, graph 1 6 Complete, matching 212 213 219 Component 5 Component, (x, y)-split 73 76 77 Component, C 8 Component, determined by the 163 Component, odd 20 Component, split 71 Condition I 67 75 Condition II 73 74 75 76 Configuration 84 Connected 5 Connected, component 5 65 71 Connected, internally 4 173 Connected, subgraph 5 Connectivity problem 29 Conservation rule 186 Contraction 4 11 Convex, drawing 65 66 70 75 76 79 Convex, polygon 65 66 Convex, testing 65 70 CONVEX-DRAW 69 CONVEX-TEST 79 Cook, S.A. 24 26 Cover 168 170 Cover, vertex 21 168 CPATH 114 Critical, graph 104 Critical, separation pair 73 75 76 77 78 79 Cut 5 193 Cut, condition 193 194 198 199 210 216 Cut, minimum 189 Cutset 5 16 193 194 Cutvertex 5 CYCLE 5 16 Cycle, 78 79 Cycle, basis 17 Cycle, facial 7 66 75 76 78 Cycle, Hamiltonian 171 Cycle, odd 112 Cycle, separator 149 Cycle, space 15 17 Data structure 27 Degree 3 11 Degree, maximum 10 108 111 Degree, minimum 19 20 21 DEGREE3 125 DEGREE4 126 DEGREE5 127 DELTAFLOW 197 198 demand 186 Depth-first number 34 Depth-first search (DFS) 29 34 Depth-first-search 30 Descendant 34 Determined by the component 163 Deterministic algorithm 25 DFS 35 52 DFS-tree 53 Diameter 153 158 Digraph 3 Digraph, upward 40 53 Dijkstra's algorithm 191 Directed graph 3 209 Direction indicator 55 Disconnected 5 Divide and conquer 149 171 184 214 Domain 157 Domain, directly 157 Domain, tree 157 doubly linked list 27 Drawing 65 Drawing, convex 65 66 70 75 76 79 Drawing, straight line 76 Dual, combinatorial 16 17 18 Dual, geometric 15 16 Dual, graph 15 EDGE 2 Edge, back 30 37 Edge, blocking 218 Edge, c 113 Edge, coloring 99 119 Edge, deletion 131 133 Edge, multiple 3 Edge, negative 210 Edge, searching 138 Edge, tree 30 37 Edge, virtual 40 71 172 Eliminable 104 107 108 111 112 Embed 7 Embedding 7 33 34 40 51 53 63 79 Embedding, algorithm 49 Embedding, upward 40 53 57 62 ENTIRE-EMBED 52 Equivalent embedding 7 Euler's formula 9 Euler, L. 9 Even, S. 33 34 140 Exploring a graph 29 Exponential algorithm 25 Extendible, convex polygon 66 Extendible, facial cycle 66 Face 7 9 15 Face, infinite 7 Face, outer 7 Facial cycle 7 66 75 76 78 172 177 Facial cycle, extendible 66 Fan sequence 101 Father 34 Feasibility 195 210 214 Finite graph 3 Fiorini, S. 112 First-In, First-Out 27 Five 89 FIVE-COLOR 86 Five-color theorem 84 Flow 185 186 Flow, integral k-commodity 200 Flow, k-commodity 185 186 195 214 219 Flow, maximum 185 189 Flow, multicommodity 185 191 209 210 Flow, network 186 Flow, single-commodity 185 189 Forbidden graph 11 Forbidden separation pair 73 75 76 77 78 79 Ford, L.R. 185 Forest 6 164 Frederickson, G.N. 87 93 95 191 Front 153 Front, of a face 153 Front, tree 153 Fulkerson, D.R. 185 Full node 42 56 Gabow, H.N. 210 213 Galil, Z. 210 213 Gaussian elimination method 65 Gaussian elimination method, sparse 65 Geometric dual 15 16 Goldberg, M. 100 Gouyou-Beauchamps, D. 171 Graph 1 2 Graph, bipartite 6 10 Graph, complete 1 6 Graph, critical 104 Graph, directed 3 Graph, dual 15 Graph, finite 3 Graph, forbidden 11 Graph, grid 151 Graph, maximal planar 10 Graph, multi 3 15 113 118 Graph, planar 1 6 7 11 108 Graph, plane 7 Graph, random 112 Graph, representation 27 Graph, series-parallel 111 112 Graph, simple 3 Grid graph 151 Hakes, W. 84 Halting problem 23 Hamiltonian, cycle 171 Hamiltonian, path 171 177 Hamiltonian, walk 184 Hassin, R. 191 Hereditary 163 Holyer, I.J. 99 118 Hopcroft, J.E. 33 79 Horizontal separation pair 174 HPATH 182 183 Identification 85 131 133 incident 3 Independent 121 161 164 Independent, set 19 26 121 127 INDEPENDENT-SET 123 Induced, subgraph 3 161 Induced, weight 153 Infinite face 7 Internally 4-connected 172 173 175 177 Itai, A. 140 Johnson, D.B. 191 Join 3 K3 141 Kainen, P.C. 84 Karp, R.M. 26 Kashiwagi, K. 99 100 Kikuchi, S. 171 Kuratowski 11 Kuratowski's theorem 11 23 Last-in, first-out 27 Leaf 41 Lempel, A. 33 Length of a walk 4 Level 134 161 Lexico.test 147 Linear algorithm 29 Lipton, R.J. 121 149 151 160 161 162 170 210 LIST 27 List, doubly linked 27 Loop 3 Lowpoint 34 LP (linear programming) 185 Lueker, G.S. 33 42 48 MacLane's criterion 17 MacLane, S. 17 Margin 195 Matching 20 Matching, complete 212 213 219 Matching, maximum 20 213 Matsumoto, K. 191 210 213 Matula, D.W. 87 95 Max Flow-Min Cut Theorem 185 MAX-CLIQUE 145 Maximal, clique 137 138 144 147 Maximal, connected subgraph 5 Maximal, planar graph 10 184 Maximality test 144 Maximum independent set 19 121 Maximum, degree 108 111 Maximum, face size 152 153 158 Maximum, flow 185 189
Реклама
|
|
О проекте