acyclic orientation, 58
admissible colors, 153
algorithm
LST, 24
connected sequential, 12
Depressive, 101
effective, 24
First-Fit (FF),
23
greedy, 23, 62
greedy independent sets, 14
k-absolute approximation, 4, 61
k-approximation, 62
largest-first (LF), 9, 76
on-line, 21
polynomial time approximation, 61
random sequential, 9
recolor, 18
relative approximation, 4
saturation LF (SLF), 13, 77
Scattered Coloring
(SCC),
30
sequential coloring, 8
SLI, 12
smallest-last (SL), 10, 49, 76
T-DSATUR, 77
T-LF, 76
T-SL, 76
arc expansion, 145
backtracking method, 58
benchmark, 6
Bk,
61
bull, 19
cactus, 4, 76, 110
cartesian product, 108
channel assignment, 32
chromatic sum, 55, 58, 59
Chvatal's Art Gallery Theorem, 177
clique, 2
Cn,
61
cograph, 63, 82
colliding paths, 139
color interchange, 8
color requirement function, 63
Index
203
coloring
best, 55
critical, 165
equitable, 35
greedy, 8
harmonious, 95
k-total, 50
line-distinguishing, 96
of a path, 139
partial harmonious, 100
r-circular, 124, 128
r-fractional, 125
total equitable, 51
vertex, 3
comet, 40, 48, 99
complete network, 163
contiguous multichromatic sum, 64
convex, 173
hull, 173
quadrilateral, 182
quadrilateralization, 182
core of graph, 2
Cr,s,
99
cycle, 3, 76, 98
cyclic production systems, 133
cylinder, 112
D-assignment, 157
~-Equitable
Coloring Conjecture, 38
dart, 64
deficiency, 105
degree of vertex, 1
density, 1
diagonal
internal, 180
digraph
symmetric, 141
dipath, see also path, directed
distance
between vertices, 2
distributed resource allocation, 64
division rule, 164
Dynamic Storage Allocation problem (DSA),
31
Previous Page Next Page