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

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

blank
blank
blank
Красота
blank
Nishizeki T., Chiba N. — Planar Graphs: Theory and Algorithms (North-Holland Mathematics Studies)
Nishizeki T., Chiba N. — Planar Graphs: Theory and Algorithms (North-Holland Mathematics Studies)

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

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

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



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


Название: 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.


Язык: en

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

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

ed2k: ed2k stats

Издание: 1st edition

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
${K}_{3, 3}$      2 11 12 17 23
${K}_{5}$      2 11 12 17 23
${K}_{N}$      6
${K}_{s, r}$      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 $({K}_{s, r})$      1 6
Complete, graph $({K}_{n})$      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, $\nu$      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
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2019
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте