Golumbic M.C., Trenk A. — Tolerance Graphs :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Golumbic M.C., Trenk A. — Tolerance Graphs

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

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

Название: Tolerance Graphs

Авторы: Golumbic M.C., Trenk A.

Аннотация:

Primarily for researchers and graduate students, but also perhaps advanced undergraduate mathematics students, Golumbic (U. of Haifa) and Trenk (Wellesley College, Massachusetts) collect and survey the major results of tolerance graphs since they were introduced in 1982 by Golumbic and Monma to solve scheduling problems when resources are generally needed for exclusive use, but can be shared or relinquished when exclusive use is not possible. Chapter-end exercises are included

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

$(\mathcal{I}, f)$ (point-core bitolerance representation)      87
$(\mathcal{I}, p, q)$ (bounded bitolerance representation)      85
(chordless cycle on k vertices)      9
(right diagonal)      92
$D^{\uparrow}(P)$       233
(degree of the vertex u)      10
(left diagonal)      92
(edge set of enhanced graph)      74
(completion edges)      75
(optional edges)      77
(forbidden edges)      77
$F dim \leq 2$ (Ferrers dimension $\leq 2$ )      222
$gr(G, \prec)$ (Grundy number)      42
$G^* = (P \cup N, E^*)$ (enhanced graph)      74
(subgraph of G induced by $X \subseteq V(G)$ )      5
(normalization of /)      129
(covering intervals)      120
(non-covering intervals)      120
$I_x \ll I_y$ (relation between intervals)      12
$kappa\(G)$ (clique cover number)      137
(extreme lower corner)      127
$P = (X, \prec)$ (ordered set)      13
$P^d = (X, \prec^d)$ (dual)      13
$R_i \ll R_j$ (relation between ribbons, trapezoids, parallelograms)      18
(k-sun)      22
      33
      56
(left tolerance)      85
(right tolerance)      85
(tolerance)      5
(extreme upper corner)      127
$x \rightarrow y$ (single arc from x to y)      219
$x \rightleftharpoons y$ (double arc between x and y)      219
$\alpha(G)$ (stability number)      137
$\bar{B}$ (Berlin graph)      39
$\bar{G}$ (complement of graph G)      8
$\chi(G)$ (chromatic number)      40 136
$\langle\mathcal{I}, t\rangle$ (tolerance representation)      5
$\mathbb{R}^+$ (positive real numbers)      5
$\mathbb{T}$ (host tree)      164
$\mathcal{B}(X)$ (order of extreme corners)      128
$\mathcal{L}(x)$ (predecessor set)      126
$\mathcal{N}(v)$ (open neighborhood)      7
$\mathcal{N}[v]$ (closed neighborhood)      10
$\mathcal{N}^+(u)$ (out-neighbors)      219
$\mathcal{U}(x)$ (predecessors of all successors)      126
$\omega(G)$ (clique number)      40 136
$\Phi$       20
$\phi$ -tolerance chain graph      195 215
$\phi$ -tolerance graph      193
$\prec_c$ (central extension)      103
$\tilde{P}$ (less than or incomparable to digraph)      225
$\tilde{P}_1\cap\tilde{P}_2$       225
$\vec{G}^r$ (reversal of G)      219
50% tolerance graph      47 48 100
50% tolerance order      87 98
Admissible      42 43
Admissible ordering      42
Alternately orientable      38 39 48
Antichain      13
Archimedean $\phi$ -tolerance graph      201
Archimedean graph      201
Archimedean tolerance functions      201
Asteroidal triple      10 54 245
AT-free      11 20 54 60
Autonomous set      111
avoiding      244 (see also “z-avoiding”)
B(P)      126
Beads on a wire      115 230 232
Betweenness Problem      79
Bipartite graph      53 60
Bipartite order      152
Bitolerance graphs and orders      84
Block      205
Bounded bitolerance digraph      223 225 226 235 237 238
Bounded bitolerance graph      86
Bounded bitolerance order      85 94 110 146 147
Bounded bitolerance representation      85 223
Bounded NeST      176 177
Bounded NeST graph      177
Bounded tolerance digraph      229
Bounded tolerance graph      5 29 34 48 53 60 68 94 136 195
Bounded tolerance order      85 88 92 110 113
Bounded tolerance representation      47 85
Box embedding      127
BT-indexing condition      153
c(v) (center point)      86
c-point      57
Cactus      206
Caterpillar      54 238 242
Caterpillar with toes      54 58
Central extension      103
Chain      13
Chain (x - y chain)      244
Chain cover      107
Chain graph      195
Characteristic point      57
Chord of a cycle      7
Chordal graph      7 8 11 20 36 76 165 195
Chordless cycle      9
Chordless sun      201
Chromatic number      136
CLIQUE      4
Clique cover number      137
Clique number      136
Clone      63
Closed neighborhood      10
Co-perfectly orderable graph      42 48
Cocomparability graph      10 11 13 18 20 34 48 53 54 60 86 136
Coloring EPT graphs      167
Coloring intervals      11
Coloring of a graph      4
Coloring probe graphs      74 82
Coloring tolerance graphs      136
Coloring tolerance representations      137
Comparability graph      9 10 13 33 37 109
Comparability invariant      109 113
Comparable      13
Complement      8
complete      48
Complete bipartite graph      208
Complete hierarchy      48 67
Complete subgraph      4
Complexity of Interval Graph Sandwich Problem      79
Complexity of Probe Graph Sandwich Problem      81
Complexity of recognizing bounded tolerance graphs      133
Complexity of recognizing comparability graphs      10
Complexity of recognizing interval graphs      11
Complexity of recognizing permutation graphs      133
Complexity of recognizing tolerance graphs      136
Complexity of recognizing transitive orientations      10
Complexity of recognizing trapezoid graphs and orders      124 133
Complexity of recognizing weakly chordal graphs      21
Complexity of sandwich problems      78
Constant core      47 94 95 98 151
Constant tolerance NeST      176 179
Constant tolerances      31 151 194
Containment graph      168 183
Containment NeST      176 182
Core      151
Cotree      53
CoTT graph      187 195 197 198 216
Covering      13
Crown      154
Cutpoint      205
Cutset      41
d(p, q) (distance in tree)      169
Degree      10
Degree partition      23
diam(r)(diameter)      169

Diameter      169
Diasteroidal triple      244 245
Digraph      219 (see also “Directed graph”)
dim(B(P))      124
dim(P) (dimension)      14
DIMENSION      14 110 113 125
Directed graph      219
Distinct endpoints      90
Distinct tolerances      90
Distinct tolerant points      90
Double arc      219
Dual      13
E(G) (the edge set of a graph G)      1
Edge intersection graph      165
Elementary reversal      111 112
Embedded star      188
Enhanced edge      74 75
Enhanced graph      74
EPT graph      166
Equidistant centers      188
Even pair      41
Extreme lower corner      127
Extreme upper corner      127
F dim(G) (Ferrers dimension)      222
Ferrers digraph      221
Ferrers dimension      220 222 225
Function diagram      17
Function graph      18
G(V, E) (a graph G with vertex set V and edge set E)      1
Gallai      112
Geometric interpretations      91
Graph sandwich problem      77
Grundy number      42
Hasse diagrams      13
Helly property      172
Hereditary      29
Hereditary property      5
hierarchies      48
Hierarchy of $\phi$ -tolerance chain graphs      195
Hierarchy of bounded bitolerance digraphs      230
Hierarchy of bounded bitolerance orders      147
Hierarchy of containment graphs      184
Hierarchy of NeST graphs      186
Hierarchy of perfect graphs      48 49
Hierarchy of probe graphs      68
Hierarchy of ribbon graphs      17
Hovering witness      138
idim(P) (interval dimension)      15 124
IGSP      78
Implication class      9
Inc(A) (incomparable to A)      111
Incomparability graph      13 224
Incomparable      13
Independent set      4
Induced subgraph      5
Intersection graph      4 165
Interval catch digraphs      245
Interval completion      65
Interval containment graph      32
Interval dimension      15 92 94 110 124
Interval graph      1 4 11 31 47 48 54 68 84 100 195 196 198 245
Interval Graph Sandwich Problem      78 79
Interval order      13 14 84 98
Interval probe graph      65 66
Interval realizer      15 124
Interval two-point digraph      220 222
Interval two-point representation      220
Isolated vertex      23 30 196
L(v) (left endpoint)      30
Left diagonal      92
Left tolerance      85
Left-leaning representation      92
Left-right clique partition      204
Linear extension      14
Linear order      13
Linear realizer      14 113 125
Loop      219
m-star      184
Max-tolerance      194
Max-tolerance chain graph      195 196
Max-tolerance graph      203
Maximum cardinality search      7
Maximum weight stable set in a tolerance graph      140
Min-tolerance chain graph      195 196
Min-tolerance graphs      193
Neighborhood      7
Neighborhood subtree      169 170
Neighborhood subtree intersection graph      179
Neighborhood subtree tolerance graph      173
Nest      173
NeST, bounded NeST      176 177
NeST, constant tolerance NeST      176 179
NeST, containment NeST      176 182
NeST, proper NeST      176 177
NeST, unit NeST      176 177
Nonassertive vertices      56
Normal $Fdim \leq 2$ representation      222
Normal representation      57
Normalized      196
NP-complete      79 81
Odd chord      21
Order autonomous set      111 112
Ordered graph      42
Ordered set      13
Orders      13
Out-neighbors      219
P -normalization      129
p(v) (left tolerant point)      85
Parallelogram graph      18 34 48 136
Parallelogram order      91 92 147
Partitioned probe graph      73
Path graphs      166
Perfect elimination ordering      7
Perfect graph      40 43 45 48
Perfectly orderable      43 44
Perfectly orderable graph      42
Permutation diagram      16
Permutation graph      15 31 32 48 54 60
PGSP      81
Phi-tolerance      193 (see also “ $\phi$ -tolerance”)
Point-core bitolerance digraph      229 231 244 245
Point-core bitolerance order      86 95 146
Point-core order      87
Point-core tolerance digraph      232
Point-core tolerance order      98
Polynomial time      247
Posets      13
Pred(A) (predecessor set)      111
Predecessor set      125
Probe      64
Probe graph      65 68
Probe Graph Sandwich Problem      81
Proper $\phi$ -tolerance graph      215
Proper bitolerance digraph      229 237 242 244
Proper bitolerance order      86 104 147
Proper interval graph      12 45 48 67 68
Proper interval order      147 151
Proper NeST      177
Proper NeST graph      177
Proper point-core bitolerance order      150
Proper point-core tolerance order      151
Proper probe graph      67 68
Proper sum-tolerance graph      195 216
Proper tolerance graph      45 68
Proper tolerance order      147
Proper totally bounded bitolerance order      150
q(v) (right tolerant point)      85
R(v) (right endpoint)      30
Realizer      14 113 125
Reasoning about time      25

1 2

О проекте