Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
580
cut
516,529
four-point
310
metric
517,529
parity
354,442
cone
15
correlation
53,434
cut
37,391,430
cycle
438
even
cut
399,506
finitely
generated
15
Hamming
37
hypermetric
69
inequicut
399,506
integer
14
integer cycle
444
k-uniform
cut
399,507
negative
type
69,527-534
normal
534
polyhedral
15
positive semidefinite
20
semimetric
28,306,430
simplex
16
supporting
534
conic hull
14
connected
distance
space
175
connected
graph
13
contact
polytope
178
contraction
of
an
edge
12
contraction
of
an
element
437
convex [d-convex]
42
convex
body
14
convex hull
14
convex
set
14
correlation
cone
53
434
correlation
polytope'
53,434
correlation
triangle
inequalitv
423
correlation
vector
53
-
I·
64
cosimple
436
covariance
M-
58
{O,
1}-
58
covariance
mapping
56,401,435
covering
radius
172,214
Crofton
formula
111
cross-polytope 16,207
crossing
cut
semimetrics
147
cut 11,133
Chvatal
428
cut
condition
516,529
cut cone
37,391,430
Subject Index
cut
lattice
93,181,381-385
cut
polytope
37,430
cut
semi metric 28,37
even
383,399
even
T-
383
k-uniform
382,399
odd
383
cut
vector
399
cycle
13,436
cycle cone
438
cycle inequality
431
cycle
lattice
442
cycle polytope
438
cycle space
436
d-convex 283
d-split
145
data
structure
162
degree
11
Delaunay polytope
179
asymmetric
183
basic
180,443
centrally
symmetric
183
extreme
218,224,234-250
generating
180
irreducible
185
rank
of
218
reducible
185
type
of
181
Delaunay
polytope
graph
208
Delaunay polytope space
180
deletion
of
an
12
deletion
of
an
element
437
~y
-operation
392
~-system
344
demand
of
an
edge
132
design
(r,>.,n)-
342
extension
of
a
344
Hadamard
343
determinant
of a
lattice
178
diameter
of
a
graph
251
dimension
14
€p-
29,75-80,138-159
isometric
279
metric
159
direct
product
101
direct
sum
179
disconnected
graph
13
distance
27
biotope
119
circular decomposable
91
Subject
Index
Hamming
28,279
hexagonal
165
Kalmanson
91
Lee
166
octogonal
164
quasi
h- 385-391
spherical
86
Steinhaus
118
truncated
251
distance
matrix
27,277,291-293
Euclidean 75,527-534
distance
space
27
connected
175
elliptic
87
spherical
86
strongly
even 175,210-211
distance-regular
graph
267,309
distortion
125
distributive
lattice
106
dual
BIBD
342
dual
Fano
matroid
438
dual
lattice
179
dual
matroid
436
duplication
operation
418,500-502
edge
11
edgeweight vector
400
8-metric
164
ii-embeddable
39-42
ii-graph
251,280,312-330
iI-rigid
44
ii-rigid
graph
280,314,325
iI-size
minimum
45
ip-dimension 29,75-80,138-159
minimum
29,76,138-159
ip-embeddable
29
ip-metric
28
l;:"-embeddable
30
elliptic
distance
space
87
elliptope 462,515-527,534-539
embeddable
lp-
29
l;:"-
30
hypercube
30,40-41
isometrically
29
32-35
embedding
A-
313
Lipschitz 124-132
empty
ellipsoid
188
empty
sphere
179
endnode
11
equicut
399
equicut
polytope
399,506
equidistant
metric
28,46,95,98-101,
334-352
581
equivalent
hypercube
embeddings
45
Euclidean
distance
matrix
75,527-534
Eulerian
graph
13
even
cut
cone
399,506
even
cut
semimetric
383,399
even
lattice
178
even
T-cut
semimetric
383
extension
antipodal
94,98-101
full
antipodal
94
gate
93
gate
0-
93
spherical t- 97,213-216
extension
of
a design
344
extremal
graph
375
extreme
Delaunay
polytope
218,224,
234-250
extreme
point
535
extreme
ray
17
face
16
automorphism
of
a
408
orbit
of
a
407
simplex
17
facet
16
Fano
matroid
437
Fibonacci inequality
499
finitely
generated
cone
15
folded
n-cube
graph
410
forest
13
4-metric
164
four-point condition
310
full
antipodal
extension
94
full-dimensional
14
gap
inequality
457-458
gate
extension
93
gate
O-extension
93
general
lattice
181
general position
538
generalized
bipartite
metric
357-361
generalized line
graph
259
generalized line
graphs
266
generating
Delaunay
polytope
180
generating
set
177
affine
178
582
gonal inequality
k-
68
Gosset
graph
208,240
Gosset polytope 208,240
Gram
matrix
20
graph
11
atom
316
bipartite
11
chordal
517
Clebsch
209
cocktail-
party
12,98-101,207,313
complete
11
complete
bipartite
11
connected
13
Delaunay
polytope
208
disconnected
13
distance-regular 267,309
£1-
251,280,312-330
Eulerian
13
extremal
375
folded
n-cube
410
Gosset
208,240
half-cube 12,207,313,315
Hamming
280,303
hypercube
12
hypercube embeddable
277,
282-293
hypermetric 251,277,287-290
interval-regular
309
irreducible
297
Johnson
207
line
14
minor
of a
12
negative
type
251,277,287-291
1-skeleton
16
outerplanar
330
path-block-cycle
493
Petersen
13
regular
262
Schliifli
208,240
semi regular
264
series-parallel
518
strongly
regular
268
support
400
suspension
14
triangular
209
uniformely geodetic
309
graph
factoring problem
305
graphic metric space 29,277
great
circle metric
86
grid metric
164
Subject Index
Grishukhin's inequality
502
h-Iabeling
334
h-realization
matrix
44,333
h-rigid 44,334-340
h-size
minimum 45,347-350
Hadamard
design
343
Hadamard
matrix
237,343
half-cube
207
half-cube
graph
12,207,313,315
Hamming
cone
37
Hamming
distance 28,279
Hamming
graph
280,303
Hamming
space 42-43
hexagonal distance
165
Hilbert basis 391-393,444
Hlawka's inequality
110
hole
179
homeomorph
520
homothety
224
hull
affine integer
14
conic
14
convex
14
integer
14
hypercube
16
squashed
293
hypercube embeddability problem
353
hypercube embeddable 30,40-41
hypercube embeddable
graph
277,
282-293
hypercube
graph
12
hypercube metric space
29
hypermetric 67-86
hypermetric cone
69
hypermetric
graph
251,277,287-290
hypermetric inequality 68,444-465
hypermetric space
rank
of
218
incidence vector
14
induced
subgraph
12
inequality
bicycle
odd
wheel
469
circulant 496-497
clique-web 467-485
cocycle
439
correlation triangle
423
cycle
431
Fibonacci
499
gap 457-458
Subject Index
Grishukhin's
502
Hlawka's
110
hypermetrk
68,444-465
k-gonal
68
negative
type
68
parachute
497-502
path-block-cycle 492-496
pentagonal
68
pure
68,400
rooted
triangle
425
suspended-tree 487-492
triangle
27,420-435
valid
17
inequicut
399
inequicut cone
399,506
inertia
21
Sylvester's law
of
21
integer cone
14
integer cycle cone
444
integer hull
14
integral
lattice
178
intersection
pattern
355
interval-regular
graph
309
irreducible Delaunay polytope
185
irreducible
graph
297
irreducible
lattice
179
irredundant
isometric embedding
297
isolation index
145
isometric dimension
279
isometric embedding
29
isometric
subgraph
29,277
isometric subspace
29
isometrically embeddable
29
isomorphic
graphs
12
isotone valuation
105
Johnson
graph
207
k-framework
166
k-gonal inequality
68
k-grill
166
k-neighborly polytope
539
k-uniform
cut
cone
399,507
k-uniform
cut
semimetric
382,399
Kalmanson
distance
91
kernel
189
L-decomposition
182
L-polytope
179
L-type
domain
188
L1-embeddable 41-42
Lp-embeddable
32-35
Lp.norm
32
L
2
-embeddable 73-83
A-embedding
313
lattice
lattices
affine
178
Barnes-Wall
245
centered
250
cut 93,181,381-385
cycle
442
distributive
106
dual
179
even
178
181
integral
178
irreducible
179
Leech
244
metric
105
modular
106
perfect
248
point
177
poset
105
reducible
179
root 178,206-209
self-dual
179
special
181
star
of
a
181
type
of
181
unimodular
179
z-equivalent
181
leaf
142
Lee distance
166
Leech
lattice
244
lifting
0-
413
lifting
operation
413-416
line
graph
14
generalized
259
linear description
15
583
linear
programming
duality
theorem
17
linear programming problem
17
dual
17
Lipschitz embedding 124-132
M-c1ique
372
M-stable
set
372
mtp(n)
30
Manhattan
metric
164
mapping
covariance 56,401,435
switching
404
matching
12
584
matrix
perfect
12
adjacency
251
distance
27,277,291-293
Gram
20
h-realization
44,333
Hadamard
237,343
orthogonal
19
positive semidefinite
20
realization
44
unimodular
178
matroid
binary
435-444
dual
436
dual
Fano
438
Fano
437
max-cut
problem
38,434
max-flow
133
maximum
weight cycle problem
441
measure
32
cardinality
32
measure
semimetric
33
measure semimetric space
33
measure space
32
metric
27
Chebyshev
164
chessboard
164
city-block
164
8-
164
fip-
28
equidistant
28,46,95,98-101,
334-352
4-
164
generalized
bipartite
357-361
great
circle
86
grid
164
Manhattan
164
Minkowski
28
norm
28,109-111
path
29
projective
111
rectilinear
164
6-
165
taxi-cab
164
tree
147,310
uniform
164
metric condition
517,529
metric dimension
159
metric
lattice
105
metric
representation
297
canonical
298
metric space
graphic
29,277
hypercube
29
metric
transform
113
minimal norm
178
minimal vector
178
minimum
J'I
-size
45
Subject Index
minimum lp-dimension 29,76,138-159
minimum h-size 45,347-350
minimum scale
47,280
Minkowski metric
28
minor
of
a distance
146
minor
of
a
graph
12
minor
of
a
matroid
437
modular
lattice
106
multicommodity flow
132-137
multicut polytope
399
multicut semimetric
42
negative type 67-86
negative type cone 69,527-534
negative
type
graph
251,277,287-291
negative
type
inequality
68
neighborly polytope
k-
539
nested
140
m-
140
node
11
node splitting operation
416,520
norm
28
Lp-
32
minimal
178
norm metric 28,109-111
normal cone
534
objective function
17
octogonal distance
164
odd
cut
semimetric
383
I-skeleton
graph
16
I-sum
103
operation
collapsing
410-413
LlY-
392
duplication 418,500-502
lifting 413-416
node splitting
416,520
switching 403-409
switching
by
roots
404
lB4--realization
43
orbit
of
a face
407
order
of congruence
29,79,89,370
order polytope
427
Subject
Index
orthogonal
matrix
19
outer
planar
graph
330
Z~-realization
43
parachute
inequality
497-502
parallelotope
85
parity
condition
354,442
partial
projective plane
336
path
12
path
metric
29
path-block-cycle
graph
493
path-block-cycle inequality 492-496
pentagonal
inequality
68
perfect
lattice
248
perfect
matching
12
permutation
equivalent inequalities
403
Petersen
graph
13
point
lattice
177
pointed
at
the
position
56
polar
14
polyhedral cone
15
polyhedron
15
polynomial reduction
19
polytope
15
Bell-Wigner
54
bipartite
subgraph
496
boolean quadric
54
contact
178
correlation 53,434
cut
37,430
cycle
438
Delaunay
179
equicut
399,506
Gosset
208,240
k-neighborly
539
L-
179
multicut
399
order
427
repartitioning
226
rooted semimetric
425
Schliifli
208,240
semimetric
421,430
Voronoi
182
poset
lattice
105
positive semidefinite completion problem
462,515-527
positive semidefinite cone
20
positive semidefinite
matrix
20
positive
type
73-75,115
power
transform
120
primitive semimetric
306
prism
with
base
184
probability space
32
problem
Boole
61-65
concurrent flow
132
graph
factoring
305
hypercube embeddability
353
linear programming
17
max-cut
38,434
585
maximum weight cycle
441
positive semidefinite completion
462,515-527
unconstrained
quadratic
0-1
programming 54,435
product
Cartesian
13
direct
101
tensor
102
projective metric
111
projective plane
335
partial
336
proper
atom
316
pure inequality
68,400
pyramid with base
185
quadratic
form
20
quasi h-distance 385-391
Ramsey number
370
rank
14
Chvatal
428
rank
of
Delaunay polytope
218
rank
of hypermetric space
218
rank
of
matroid
437
realization
affine
219
llt-
43
Z~-
43
special
358
realization
matrix
44
h-
44,333
rectilinear metric
164
reducible Delaunay polytope
185
reducible
lattice
179
regular
graph
262
repartitioning polytope
226
representation
175
metric
297
spherical
175
representation
matrix
437
ridge
graph
543
rigid
586
h- 44,334-340
root
figure
188
root
lattice 178,206-209
root
of
an
inequality
400
rooted
semimetric polytope
425
rooted
triangle inequality
425
Rubik's
n-cube
166
scale
47
minimum 47,280
Schliifli
graph
208,240
Schliifli polytope 208,240
Schoenberg
transform
115
Schur complement
22
self-dual
lattice
179
semimetric
27
cut
28,37
even
cut
383,399
measure
33
multicut
42
primitive
306
semimetric cone
28,306,430
semimetric polytope
421,430
semimetric space
measure
33
semiregular
graph
264
series-parallel
graph
518
set
affine generating
178
basic
180
convex
14
generating
177
shore
139
a-algebra
32
simplex
16
simplex cone
16
6-metric
165
size
45
space
minimum
£1-
45
minimum h- 45,347-350
cycle
436
Delaunay
polytope
180
distance
27
graphic
metric 29,277
hypercube
metric
29
measure
32
measure semimetric
33
probability
32
special
lattice
181
special realization
358
Subject Index
spherical distance
86
spherical distance space
86
spherical representation
175
spherical t-extension 97,213-216
split-prime
145
split-prime residue
146
squashed hypercube
293
star
[graph]
11
star
embedding
335
star
of
a lattice 181
star
realization
335
Steinhaus distance
118
strongly even distance space 175,210-211
strongly regular
graph
268
subdividing an edge
520
subgraph
12
basic
242
induced
12
subspace
sum
isometric
29
direct
179
1-
103
sums
of
circuits
property
439
support
graph
400
supporting
cone
534
suspension
graph
14
switching by
roots
operation
404
switching
mapping
404
switching
operation
403-409
switching
the
inequality
404
Sylvester's law
of
inertia
21
symmetric BIBD
342
symmetric difference
14
symmetry
of
a polytope
409
system
(r,
A)-intersecting
344
~-
344
taxi-cab metric
164
tensor
product
102
terminal pairs
132
tic-tac-toe
board
166
totally
decomposable
146
transform
metric
113
power
120
Schoenberg
115
transversal
372
tree
13
tree metric
147,310
triangle inequality 27,420-435
Subject Index
triangular
graph
209
trivial
design
842
embedding
885
partial
projective plane
886
truncated
distance
251
type
of
Delaunay polytope
181
type
of
lattice
181
ultrametric
811
unconstrained
quadratic
0-1 programming
problem 54,435
uniform metric
164
uniformely geodetic
graph
809
unimodular
lattice
179
unimodular
matrix
178
valency
262
valid inequality
17
valuation
105
vector
I-correlation
64
correlation
53
cut
399
edgeweight
400
minimal
178
vertex 16,534
Voronoi polytope
182
weakly compatible
146
web
467
wheel
329,521
width
548
z-equivalent lattices
181
zonoid
110
zonotope
110
587
..
~
.......
.
b~
.
~,
1995.
ISBN
,\-C;'lo-~:87'4·Q.
Springer
Springer.
Verlag,
Po
O.
BOll:ll
';
4<>.
D-'0643
Bedin,
Germany.
aha