Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
550
Chapter
31. Geometric Properties
"We
think
that
the
shape of the cut polytope is essentially given by
the
nonsimplex facets, in particular, by its triangle facets,
and
that
the
huge majority of the facets of
CUT~
are simplices which only
'polish' it."
Interestingly, each
of
the simplex facets described above has
the
following
property (31.8.3) (see Deza
and
Laurent
[1993a]
for a proof). Let F denote such
a simplex facet
and
let 8(Sk)
(1
~
k
~
(~))
denote
its
roots. Let d E F with
decomposition
d E
15k5
(;)
Ak8(Sk)
where
Ak
;:::
0 for all
k.
Then,
(31.8.3)
d belongs
to
the
cut
lattice
en
(i.e., if d E
ZEn
and satisfies the
parity
condition (24.1.1)),
-tL
all
A~S
are integers.
In
other words, in
the
terminology of
Part
IV, the parity condition suffices for
ensuring hypercube embeddability for the class of distances
d E
F.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9, © Springer-Verlag Berlin Heidelberg 2010
Bibliography
[1994J
W.P.
Adams
and
P.M. Dearing.
On
the
equivalence between roof
duality
and
La-
grangian
duality
for unconstrained 01-quadratic programming problems. Discrete
Applied Mathematics,
48:1-20, 1994.
[430J
[1985J
F.
Afrati, C.H.
Papadimitriou,
and
G. Papageorgiou.
The
complexity
of
cubical
graphs.
Information
and Control, 66:53-60, 1985.
[294J
[1989J
F. Afrati, C.H.
Papadimitriou,
and
G. Papageorgiou.
The
complexity
of
cubical
graphs
- Corrigendum. Information and Computation, 82:350-353, 1989.
[294J
[1977J
R. Alexander.
The
width
and
diameter
of
a simplex. Geometriae Dedicata,
6:87-94, 1977.
[82J
[1978J
R. Alexander.
Planes
for which
the
lines
are
the
shortest
paths
between points.
Illinois Journal
of
Mathematics, 22:177-190, 1978.
[111J
[1988J
R. Alexander. Zonoid theory
and
Hilbert's
fourth problem. Geometriae Dedicata,
28:199-211, 1988.
[111J
[1990J
N. Alon.
The
CW-inequalities for vectors in
£1.
European Journal
of
Combina-
tories,
11:1-5,1990.
[472J
[1994J
B. Alspach, L. Goddyn,
and
C.-Q. Zhang.
Graphs
with
the
circuit cover property.
Transactions
of
the
American
Mathematical Society, 344:131-154, 1994.
[444J
[1988J
1.
Althofer. On optimal realizations
of
finite metric spaces by graphs. Discrete
and Computational Geometry,
3:103-122, 1988.
[310J
[1982J
R.V.
Ambartzumian.
Combinatorial Integral Geometry - with Applications to
Mathematical Stereology.
John
Wiley & Sons, Chichester, 1982. [111,162J
[1987J
M. Aschbacher, P. Baldi, E.B.
Baum,
and
R.M. Wilson.
Embeddings
of
ultra-
metric
spaces in finite dimensional structures.
SIAM
Journal on Algebraic and
Discrete Methods,
8:564-577, 1987.
[311J
[1977J
P. Assouad.
Un
espace hypermetrique non plongeable
dans
un espace L
I
.
Comptes
Rendus
de
l'Academie des Sciences
de
Paris, 285(A):361-363, 1977.
[84J
[1979J
P. Assouad.
Produit
tensoriel, distances extremales
et
realisation de covariances.
Comptes
Rendus
de
l'Academie des Sciences
de
Paris, 288(A):649-652
and
675-
677, 1979. [54,58,107,108,114J
[1980aJ P. Assouad. Caracterisations de sous-espaces normes de
LI
de dimension finie.
Number
19 in Seminaire d'Analyse Fonctionnelle. Ecole Poly technique Palaiseau,
1979-1980.
[110J
[1980bJ P. Assouad. Plongements isometriques dans
V:
aspect
analytique. Num-
ber
14 in Seminaire d'Initiation a l'Analyse (G. Choquet, H. Fakhoury,
J.
Saint-
Raymond).
Universite
Paris
VI, 1979-1980. [39,54,58,108,114,119J
[1982J
P. Assouad. Sous espaces de
LI
et
inegalites hypermetriques. Comptes
Rendus
de
l'Academie des Sciences
de
Paris, 294(A):439-442, 1982. [193,198,381J
552
Bibliography
[1984J
P. Assouad.
Sur
les im\galites valides
dans
L1. European Journal
of
Combina-
tories,
5:99-112, 1984. [72,110,111,I72,193,477,497J
[1980J
P.
Assouad
and
C. Delorme.
Graphes
plongeables
dans
L1. Comptes
Rendus
de
l'Academie des Sciences
de
Paris, 291(A):369-372, 1980. [253,255,262,370J
[1982J
P. Assouad
and
C. Delorme. Distances
sur
les
graphes
et
plongements
dans
L1,
I
et
II. Technical
Report,
Universite d'Orsay, 1982. [255,257,261,262,370,477,497]
[1980] P. Assouad
and
M Deza.
Espaces
metriques
plongeables
dans
un hypercube:
aspects
combinatoires.
In
M.
Deza
and
I.G. Rosenberg, editors, Combinatorics
79 -
Part
I, volume 8
of
Annals
of
Discrete Mathematics, pages 197-210.
North-
Holland,
Amsterdam,
1980.
[356J
[1982J
P. Assouad
and
M. Deza.
Metric
subspaces
of
V.
Number
82-03 in Publications
Mathematiques d'Orsay.
Universite de
Paris-Sud,
Orsay, 1982.
[39J
[1997] Y.
Aumann
and
Y.
Rabani.
An O(log
k)
approximate
min-cut max-flow
theorem
and
approximation
algorithm.
SIAM
Journal on Computing, 1997
(to
appear).
[134]
[1991]
F.
Aurenhammer
and
J.
Hagauer.
Recognizing
binary
Hamming
graphs
in
O(n
2
10gn) time.
In
RH.
Mohring,
editor,
Graph-Theoretic Concepts
in
Com-
puter
Science, volume 484
of
Lecture Notes in
Computer
Science, pages
90-98.
Springer-Verlag, Berlin, 1991.
[286]
[1990]
F.
Aurenhammer,
J.
Hagauer,
and
W.
Imrich.
Factoring
cartesian-product
graphs
at
logarithmic
cost
per
edge.
In
R
Kannan
and
W.R
Pulleyblank,
editors,
Integer
Programming and Combinatorial Optimization,
pages 29-44. University
of
Water-
loo
Press,
1990.
(Updated
version in: Computational Complexity, 2:331-349, 1992.)
[306]
[1977] D. Avis.
Some
Polyhedral Cones Related to Metric Spaces.
PhD
thesis,
Stanford
University, 1977. [37,39,422,477]
[1980a] D. Avis.
On
the
extreme
rays of
the
metric
cone. Canadian Journal
of
Mathe-
matics,
32:126-144, 1980.
[422]
[1980b] D. Avis.
Extremal
metrics induced by
graphs.
In
M.
Deza
and
I.G. Rosenberg,
editors,
Combinatorics 79 -
Part
I, volume 8
of
Annals
of
Discrete Mathematics,
pages
217-220.
North-Holland,
Amsterdam,
1980.
[422]
[1981J
D. Avis.
Hypermetric
spaces
and
the
Hamming
cone. Canadian Journal
of
Mathematics, 33:795-802, 1981. [84,286]
[1989] D. Avis
(and
Mutt).
All facets
of
the
six point
Hamming
cone. European Journal
of
Combinatorics, 10:309-312, 1989. [229,235,503]
[1990] D. Avis.
On
the
complexity of isometric
embedding
in
the
hypercube.
In
T.
Asano,
T.
Ibaraki,
H.
Imai,
and
T.
Nishizeki, editors, Algorithms, volume 450 of
Lecture Notes in Computer Science, pages 348-357. Springer-Verlag, Berlin, 1990.
[362,369]
[1991] D. Avis
and
M. Deza.
The
cut cone,
L1
embeddability, complexity
and
multi-
commodity
flows. Networks, 21:595-617, 1991. [49,422,451]
[1993] D. Avis
and
V.P. Grishukhin. A
bound
on
the
k-gonality
of
facets
of
the
hyper-
metric
cone
and
related complexity problems. Computational Geometry: Theory
and Applications,
2:241-254, 1993. [204,205,226,453]
[1994] D. Avis
and
H.
Maehara.
Metric
extensions
and
the
L1
hierarchy. Discrete
Mathematics,
131:17-28,1994.
[214,289]
Bibliography
553
[1995] M.
Bakonyi
and
C.R.
Johnson.
The
Euclidian
distance
matrix
completion
problem.
SIAM
Journal on Matrix Analysis and Applications, 16:646-654, 1995.
[529,530]
[1993]
E.
Balas,
S. Ceria,
and
G. Cornuejols. A lift-and-project
cutting
plane
algorithm
for mixed 0-1
programs.
Mathematical Programming, 58:295-324, 1993.
[424]
[1987]
K.
Ball. Inequalities
and
sphere-packings in C
p
•
Israel Journal
of
Mathematics,
58:243-256, 1987. [34,159]
[1990]
K.
Ball.
Isometric
embedding
in Cp-spaces. European Journal
of
Combinatorics,
11:305-311, 1990. [72,157]
[1990]
H-J.
Bandelt.
Recognition
of
tree
metrics.
SIAM
Journal on Discrete Mathe-
matics,
3:1-6,
1990.
[311]
[1996a]
H-J.
Bandelt
and
V.D. Chepoi.
Embedding
metric
spaces in
the
rectilinear
plane: a six-point criterion. Discrete and Computational Geometry, 15:107-117,
1996. [141,148,152]
[1996b]
H-J.
Bandelt
and
V.D. Chepoi.
Embedding
into
the
rectilinear grid.
Preprint,
1996. [155,156]
[1996c]
H-J.
Bandelt
and
V.D. Chepoi. Weakly
median
graphs: decomposition, C
1
-
embedding
and
algebraic
characterization.
Preprint,
1996.
[330]
[1997]
H-J.
Bandelt,
V.D. Chepoi,
and
M.
Laurent.
Embedding
into
rectilinear spaces.
Discrete and Computational Geometry, 1997
(to
appear).
[141,144]
[1992]
H-J.
Bandelt
and
A.W.M. Dress. A canonical decomposition
theory
for
metrics
on
a finite set. Advances
in
Mathematics, 92:47-105, 1992. [28,56,92,145,146,147]
[1991]
H-J.
Bandelt
and
H.M. Mulder.
Cartesian
factorization
of
interval-regular
graphs
having
no long isometric
odd
cycles.
In
Y. Alavi
et
al.,
editor,
Graph Theory,
Combinatorics and Applications,
volume 1, pages
55-75.
John
Wiley & Sons, New
York, 1991.
[309]
[1981]
F.
Barahona.
Balancing signed graphs
of
fixed genus
in
polynomial time. Technical
Report,
Departamento
de
Matematicas,
Universidad de Chile, 1981.
[48]
[1982]
F.
Barahona.
On
the
computational
complexity
of
Ising spin glass models. Jour-
nal
of
Physics
A,
Mathematical and General, 15:3241-3253, 1982. [48,52]
[1983]
F.
Barahona.
The
max-cut
problem
on
graphs
not
contractible
to
Ks.
Operations
Research Letters,
2:107-111, 1983. [48,434]
[1993]
F.
Barahona.
On
cuts
and
matchings in
planar
graphs.
Mathematical Program-
ming,
60:53-68, 1993.
[431]
[1994]
F.
Barahona.
Ground-state
magnetization
of
Ising spin glasses. Physical Review
B, 49(18):12864-12867, 1994.
[52]
[1986]
F.
Barahona
and
M. Grotschel.
On
the
cycle
polytope
of
a
binary
matroid.
Journal
of
Combinatorial Theory B, 40:40-62, 1986. [405,439,440]
[1988]
F.
Barahona,
M. Grotschel, M.
Junger,
and
G. Reinelt. An
application
of
com-
binatorial
optimization
to
statistical
physics
and
circuit layout design. Operations
Research,
36:493-513, 1988. [38,51,52]
[1985]
F.
Barahona,
M.
Grotschel,
and
A.R.
Mahjoub.
Facets
of
the
bipartite
subgraph
polytope.
Mathematics
of
Operations Research, 10:340-358, 1985. [469,483]
[1989]
F.
Barahona,
M.
Junger,
and
G. Reinelt.
Experiments
in
quadratic
0-1
program-
ming. Mathematical Programming, 44:127-137, 1989. [52,56]
[1986]
F.
Barahona
and
A.R.
Mahjoub.
On
the
cut
polytope. Mathematical Program-
ming,
36:157-173, 1986. [405,431,433,434,453,469,483,539]
554
Bibliography
[1982]
F. Barahona, R. Maynard, R. Rammal, and J.-P. Uhry. Morphology
of
ground
states
of a two dimensional frustration model. Journal
of
Physics A, 15:L673-L699,
1982.
[52]
[1971]
E.P. Baranovskii. Simplexes
of
L-subdivisions of Euclidean spaces. Mathematical
Notes,
10:827-834,1971. (Translated from: Matematicheskie Zametki 10;659-671,
1971.) [69,229,235,503]
[1973]
E.P. Baranovskii. Theorem on L-partitions of point lattices. Mathematical Notes,
13:364-370,1973. (Translated from: Matematicheskie Zametki 13:605-616, 1973.)
[69,235]
[1992]
E.P. Baranovskii. Partitioning
of
Euclidean space into L-polytopes of some per-
fect lattices. In S.P. Novikov, S.s. Ryshkov, N.P. Dolbilin,
and
M.A. Shtan'ko,
editors,
Discrete Geometry and Topology, volume 196(4) of Proceedings
of
the
Steklov Institute
of
Mathematics, pages 29-51. American Mathematical Society,
Providence, Rhode Island, 1992.
[181]
[1995]
E.P. Baranovskii. In
the
Second International
Conference'
Algebraic, Proba-
bilistic, Geometrical, Combinatorial, and Functional Methods in
the
Theory of
Numbers', September 1995, Voronezh, Russia.
[229]
[1996]
W.W.
Barrett,
C.R. Johnson,
and
R. Loewy.
The
real positive definite completion
problem: cycle completability.
Memoirs
of
the American Mathematical Society,
Number 584, 69 pages, 1996.
[521,522J
[1993J
W.
Barrett,
C.R. Johnson,
and
P. Tarazaga. The real positive definite completion
problem for a simple cycle.
Linear Algebra and its Applications, 192:3-31, 1993.
[514J
[1995J
A.I. Barvinok. Problems of distance geometry
and
convex properties
of
quadratic
maps. Discrete and Computational Geometry, 13:189-202, 1995.
[528]
[1970]
L.W. Beineke. Characterization
of
derived graphs. Journal
of
Combinatorial
Theory,
9:129-135, 1970.
[254]
[1976]
C. Berg, J.P.R. Christensen,
and
P. Ressel. Positive definite functions on abelian
semigroups.
Mathematische Annalen, 223:253-272, 1976.
[107]
[1987]
M.
Berger. Geometry II. Springer-Verlag, Berlin, 1987.
[514J
[1980]
I.
Bieche, R. Maynard, R. Rammal,
and
J.-P. Uhry. On
the
ground
states
of
of
the
frustration model of a spin glass
by
a matching method of graph theory. Journal
of
Physics A, Mathematical and General, 13:2553-2571, 1980.
[52]
[1981]
N.L. Biggs and
T.
Ito. Covering graphs and symmetric designs. In
P.J.
Cameron,
J.W.P.
Hirschfeld,
and
D.R. Hughes, editors, Finite Geometries and Designs, vol-
ume 49
of
London Mathematical Society Lecture Note Series, pages 40-51. Cam-
bridge University Press, Cambridge, 1981.
[344]
[1967]
G. Birkhoff. Lattice Theory. American Mathematical Society, Providence, Rhode
Island, 1967. [105,106]
[1973]
I.F. Blake
and
J.H. Gilchrist. Addresses for graphs.
IEEE
Transactions on
Information Theory,
IT-19:683-688, 1973. [100,278,288,314]
[1953]
L.M. Blumenthal. Theory and Applications
of
Distance Geometry. Oxford
University Press, Oxford, 1953. (Second edition: Chelsea, New York, 1970.)
[25,29,74,76,78,80,86,87,88,113,120,514]
[1994]
H.L. Bodlaender and K. Jansen. On
the
complexity of
the
maximum
cut
problem.
In P. Enjalbert, E.W.Mayr, and K.W. Wagner, editors,
Proceedings
of
the 11th
Annual Symposium on Theoretical Aspects
of
Computer Science, volume 775
of
Lecture Notes in Computer Science, pages 769-780. Springer-Verlag, 1994.
[48]
Bibliography
555
[1994]
N. Boissin. Optimisation
des
Fonctions Quadratiques en Variables Bivalentes.
PhD
thesis,
Centre
National
d'Etudes
des Telecommunications, Issy Les Moulin-
eaux, France, 1994. [54,416,489,500)
[1969]
E.D. BoHrer. A class of convex bodies. Transactions
of
the American Mathemat-
ical Society,
145:323-345,1969.
[110]
[1976]
J.A.
Bondy
and
U.S.R. Murty. Graph Theory with Applications. American Else-
vier, New York,
and
Macmillan, London, 1976.
[11]
[1936]
C.E. Bonferroni.
II
calcolo delle assicurazioni su grouppi di teste. Studi in
OnoTe
del
Professor S.O. Carboni (Roma), 1936.
[65]
[1854]
G. Boole.
An
Investigation
of
the Laws
of
Thought on Which Are Founded the
Mathematical Theories
of
Logic and Probabilities. Dover Publications, New York,
original edition 1854.
[61]
[1990]
E.
Boros, Y.
Crama,
and
P.L. Hammer. Upper bounds for
quadratic
0-1 opti-
mization problems.
Operations Research Letters, 9:73-79, 1990.
[430]
[1992]
E.
Boros, Y.
Crama,
and
P.L. Hammer.
Chvatal
cuts
and
odd
cycle inequalities
in
quadratic
0-1 optimization.
SIAM
Journal on Discrete Mathematics, 5:163-177,
1992. [428,430]
[1991]
E. Boros
and
P.L. Hammer.
The
max-cut problem
and
quadratic
0-1 optimiza-
tion: polyhedral aspects, relaxations
and
bounds. Annals
of
Operations Research,
33:151-180,1991. [54,430]
[1993]
E.
Boros
and
P.L. Hammer.
Cut
polytopes, boolean
quadratic
polytopes
and
non-
negative
quadratic
pseudo-boolean functions. Mathematics
of
Operations Research,
18:245-253, 1993. [54,487,489]
[1989J
E. Boros
and
A. Prekopa. Closed form two-sided bounds for probabilities
that
at
least r
and
exactly r
out
of
n events occur. Mathematics
of
Operations Research,
14:317-342, 1989.
[65]
[1933]
K. Borsuk. Drei Satze iiber die n-dimensionale Euklidische Sphare. Fundamenta
Mathematicae,
20:177-190,1933. [10,512]
[1985]
J.
Bourgain.
On
Lipschitz embedding
of
finite metric spaces in Hilbert space.
Israel Journal
of
Mathematics, 52:46-52, 1985.
[125]
[1991]
S. Boyd
and
W.H. Cunningham. Small travelling salesman polytopes. Mathe-
matics
of
Operations Research, 16:259-271, 1991.
[506J
[1966]
J.
Bretagnolle, D.
Dacunha
Castelle,
and
J.-L. Krivine. Lois stables
et
espaces
LP.
Annales
de
l'Institut Henri Poincare, 2:231-259, 1966. [33,34,110J
[1989]
A.E. Brouwer, A.M. Cohen,
and
A. Neumaier. Distance-Regular Graphs.
Springer-Verlag, Berlin, 1989. [96,206,239,257,268,308,410]
[1971]
P. Buneman.
The
recovery of trees from measures of dissimilarity. In F.R.
Hodson
et
aI., editor, Mathematics in the Archeological and Historical Sciences,
pages 387-395, Edinburgh University Press, Edinburgh, 1971.
[147]
[1974]
P. Buneman. A note on metric properties of trees. Journal
of
Combinatorial
Theory B,
17:48-50, 1974.
[310]
[1995]
G. Burosch
and
P.V. Ceccherini. Isometric embeddings into cube-hypergraphs.
Discrete Mathematics, 137:77-85, 1995.
[294]
[1976]
F.C. Bussemaker, D.M. Cvetkovic,
and
J.J. Seidel. Graphs related
to
excep-
tional
root
systems.
TH-report
76-WSK-05, Technical University Eindhoven,
The
Netherlands, 1976.
[2671
556
Bibliography
[1976]
P.J.
Cameron,
J.M.
Goethals,
J.J.
Seidel,
and
E.E.
Shult. Line
graphs,
root
systems,
and
elliptic geometry. Journal
of
Algebra, 43:305-327, 1976. [93,267]
[1959]
J.W.S.
Cassels.
An
Introduction to the Geometry
of
Numbers, volume 99
of
Die
Grundlehren der mathematischen Wissenschaften
in
Einzeldarstellungen. Springer-
Verlag, Berlin, 1959.
[190]
[1841] A. Cayley.
On
a
theorem
in
the
geometry
of
position. Cambridge Mathemati-
cal Journal,
vol. II:267-271, 1841. (Also in The Collected Mathematical Papers
of
Arthur
Cayley,
Cambridge
University
Press,
pages
1-4,
1889.) [25,73]
[1986] P.V. Ceccherini
and
A.
Sappa.
A new
characterization
of
hypercubes.
In
A.
Bar-
lotti
et
aI.,
editor,
Combinatorics
84,
Annals
of
Discrete
Mathematics
30, pages
137-142.
North-Holland,
Amsterdam,
1986.
[309]
[1947] P.L. Chebyshev. Complete Collected Works -
Vol.
2.
Moscow-Leningrad (in
Rus-
sian),
1947.
[213]
[1996] V.
Chepoi,
M. Deza,
and
V.P. Grishukhin. Clin d'oeil
on
Lr-embeddable
pla-
nar
graphs.
Rapport
LIENS-96-11, Ecole
Normale
Superieure,
Paris,
1996.
[325,326,330]
[1996] V.
Chepoi
and
B. Fichet. A
note
on
circular decomposable metrics.
Preprint,
1996.
[91]
[1995] S.
Chopra
and
M.R.
Rao.
Facets
of
the
k-partition
polytope. Discrete Applied
Mathematics,
61:27-48, 1995. [400,465]
[1979]
J.P.R.
Christensen
and
J.
Vesterstrpm. A
note
on
extreme
positive definite
ma-
trices. Mathematische Annalen, 244:65-68, 1979.
[537]
[1991]
T.
Christof, M.
Junger,
and
G. Reinelt. A complete description
of
the
traveling
salesman
polytope
on
8 nodes. Operations Research Letters, 10:497-500, 1991.
[506]
[1996]
T.
Christof
and
G. Reinelt.
Personal
communication, 1996. [505,543]
[1996] G.
Christopher,
M.
Farach,
and
M.A. Trick.
The
structure
of
circular decom-
posable
metrics.
In
J. Diaz
and
M. Serna, editors, Algorithms -
ESA
'96, volume
1136
of
Lecture Notes
in
Computer Science, pages 486-500. Springer-Verlag, Berlin,
1996.
[91]
[1941] K.L.
Chung.
On
the
probability
of
the
occurrence
of
at
least m events
among
n
arbitrary
events.
Annals
of
Mathematical Statistics,
12:328-338,1941.
[63]
[1973] V. Chv;ital.
Edmonds
polytopes
and
a hierarchy of
combinatorial
problems.
Discrete Mathematics, 4:305-337, 1973.
[428]
[1980] V. Chv;ital. Recognizing intersection
patterns.
In
M.
Deza
and
LG. Rosenberg,
editors,
Combinatorics 79 -
Part
I,
volume 8 of
Annals
of
Discrete Mathematics,
pages 249-251.
North-Holland,
Amsterdam,
1980.
[356]
[1989] V. Chv;ital,
W.
Cook,
and
M.
Hartmann.
On
cutting-plane
proofs in combina-
torial
optimization.
Linear Algebra and its Applications, 114/115:455-499, 1989.
[429]
[1990a] M.
Conforti,
M.R.
Rao,
and
A. Sassano.
The
equipartition
polytope:
part
I.
Mathematical Programming, 49:49-70, 1990.
[399]
[1990b] M.
Conforti,
M.R.
Rao,
and
A. Sassano.
The
equipartition
polytope:
part
II.
Mathematical Programming, 49:71-91, 1990.
[399]
[1988]
J.H.
Conway
and
N.J.A.
Sloane. Sphere Packings, Lattices and Groups, volume
290 of
Grundlehren der mathematischen Wissenschaften. Springer-Verlag, New
York, 1988. [172,206,239]
Bibliography
557
[1991]
J.H.
Conway
and
N.J.A.
Sloane.
The
cell
structures
of
certain
lattices.
In
P.
Hilton,
F.
Hirzebruch
and
R.
Remmert,
editor,
Miscellanea Mathematica, pages
71··108. Springer-Verlag, Berlin, 1991. [206,239]
[1983]
RJ.
Cook
and
D.G.
Pryce.
Uniformly geodetic
graphs.
Ars
Combinatoria, 16-
A:55-59,
1983.
[309]
[1993]
M.
Coornaert
and
A.
Papadopoulos.
Symbolic Dynamics and Hyperbolic Groups,
volume 1539 of Lecture Notes
in
Mathematics. Springer-Verlag, Berlin, 1993.
[56]
[1973] H.S.M. Coxeter. Regular Polytopes. Dover
Publications,
New York, 1973.
[186]
[1988]
F.
Critchley.
On
certain
linear
mappings
between
inner-product
and
squared-
distance
matrices.
Linear Algebra and its Applications, 105:91-107, 1988.
[56]
[1994]
F.
Crichtley
and
B.
Fichet.
The
partial
order
by inclusion of
the
principal classes
of
dissimilarity
on
a finite set,
and
some of
their
basic properties. In B. van
Cutsem,
editor,
volume 93 of Classification and Dissimilarity Analysis, Lecture Notes
in
Statistics, pages 5-65. Springer-Verlag, New York, 1994.
[163]
[1988] G.M.
Crippen
and
T.F.
Havel. Distance Geometry and Molecular Conformation.
Research
Studies
Press,
Taunton,
Somerset,
England,
1988.
[74]
[1978]
J.P.
Cunningham.
Free trees
and
bidirectional trees as
representations
of
psy-
chological
distance.
Journal
of
Mathematical Psychology, 17:165-188, 1978.
[310]
[1977]
W.H.
Cunningham.
Chords
and
disjoint
paths
in
matroids.
Discrete Mathematics,
19:7-15, 1977.
[442]
[1994]
B.
van
Cutsem,
editor.
Classification and Dissimilarity Analysis, volume 93
of
Lecture Notes
in
Statistics, pages 5-65. Springer-Verlag, New York, 1994.
[163]
[1962] L.
Danzer
and
B.
Griinbaum.
Uber
zwei
Probleme
beziiglich konvexer
Korper
von P.
Erdos
and
von V.L. Klee. Mathematische Zeitschrijt, 79:95-99, 1962.
[183]
[1969J
E. Davidson.
Linear
inequalities for density matrices. Journal
of
Mathematical
Physics,
10(4):725-734,1969.
[64,69,477,503]
[1967] D.A. Dawson
and
D. Sankoff. An inequality for probabilities. Proceedings
of
the
American
Mathematical Society, 18:504-507, 1967.
[63]
[1991]
M.
De
Berg.
On
rectilinear link distances. Computational Geometry: Theory and
Applications,
1:13-34, 1991.
[165]
[1995] V. Deineko, R Rudolf,
and
G. Woeginger. Sometimes travelling is easy:
the
master
tour
problem.
In
P. Spirakis,
editor,
Algorithms -
ESA
'95, volume 979
of
Lecture Notes
in
Computer Science, pages 128-141. Springer-Verlag, Berlin, 1995.
[92]
[1982]
J.
de
Leeuw
and
W.
Heiser.
Theory
of
multidimensional scaling.
In
P.R
Krish-
naiah
and
L.N.
Kanal,
eds, Handbook
of
Statistics, Vol. 2, pages 285-316.
North-
Holland,
Amsterdam,
1982.
[74]
[1993a] C.
Delorme
and
S. Poljak.
Laplacian
eigenvalues
and
the
maximum
cut
problem.
Mathematical Programming, 62:557-574, 1993.
[460]
[1993b] C.
Delorme
and
S. Poljak.
Combinatorial
properties
and
the
complexity
of
a
max-cut
approximation.
European Journal
of
Combinatorics, 14:313-333, 1993.
[461,536]
[1989]
C.
De
Simone.
The
cut
polytope
and
the
boolean
quadric
polytope. Discrete
Mathematics,
79:71-75, 1989/90. [54,56]
[1992] C.
De
Simone. The Max Cut Problem.
PhD
thesis,
Rutgers
University, New
Brunswick,
USA, 1992. [454,508]
558
Bibliography
[1994] C.
De
Simone, M. Deza,
and
M.
Laurent.
Collapsing
and
lifting for
the
cut
cone.
Discrete Mathematics,
127:105-130,1994.
[410,411,463,480,502,505,508]
[1995] C.
De
Simone, M. Diehl, M.
Junger,
P. Mutzel, G. Reinelt,
and
G. Rinaldi.
Exact
ground
states
of Ising
spin
glasses: new
experimental
results
with
a
branch-and-cut
algorithm.
Journal
of
Statistical Physics, 80(1-2):487-496, 1995.
[52]
[1996] C.
De
Simone, M. Diehl,
M.
Junger,
P. Mutzel, G. Reinelt,
and
G. Rinaldi.
Exact
ground
states
of two-dimensional
±J
Ising spin glasses. Journal
of
Statistical
Physics,
84(5-6):1363-1371, 1996.
[52]
[1994] C.
De
Simone
and
G. Rinaldi. A
cutting
plane
algorithm
for
the
max-cut
problem.
Optimization
Methods and Software, 3:195-214, 1994.
[454]
[1993]
C.C.
De
Souza. The Graph Equipartition Problem: Optimal Solutions,
Extensions
and
Applications.
PhD
thesis, Universite
Catholique
de Louvain, Belgique, 1993.
[399,492,493,495,496]
[1995]
C.C.
De
Souza
and
M.
Laurent.
Some new classes
of
facets for
the
equicut
polytope.
Discrete Applied Mathematics, 62:167-191, 1995. [400,491,492,494,495]
[1980] A.K. Dewdney.
The
embedding
dimension of a
graph.
Ars
Combinatoria, 9:77-90,
1980.
[159]
[1994]
A.
Deza. Graphes et Faces
de
Polyedres Combinatoires.
PhD
thesis, Universite
de
Paris-Sud,
Orsay, France, 1994.
[542]
[1996] A. Deza. Metric Polyhedra: Combinatorial Structure and Optimization.
PhD
thesis, Tokyo
Institute
of
Technology, Tokyo,
Japan,
1996. [542,543]
[1994a] A.
Deza
and
M. Deza.
On
the
skeleton of
the
dual
cut
polytope.
In
R. Barcelo
and
G. Kalai, editors, Jerusalem Combinatorics '93, volume 178
of
Contemporary
Mathematics,
pages 101-111, 1994. [407,545,549]
[1994b]
A.
Deza
and
M. Deza.
The
ridge
graph
ofthe
metric
polytope
and
some relatives.
In
Polytopes: Abstract, Convex and Computational, volume 440
of
NATO
AS!
Series C: Mathematical and Physical Sciences, pages 359-372. Kluwer Academic
Publishers,
Dordrecht,
1994. [544,545]
[1995] A.
Deza
and
M. Deza.
The
combinatorial
structure
of small
cut
and
metric
poly-
topes.
In
T.R.
Ku,
editor,
Combinatorics and Graph Theory
95,
World Scientific
Publisher,
Singapour,
pages 70-88, 1995. [541,545]
[1996] A. Deza, M.
Deza
and
K.
Fukuda.
On
skeletons,
diameters
and
volumes
of
metric
polyhedra.
In
M. Deza, R.
Euler,
and
Y. Manoussakis, editors, Combinatorics and
Computer
Science, volume 1120
of
Lecture Notes in Computer Science, pages
112-
128. Springer-Verlag, Berlin, 1996. [542,543,544,546]
[1996] A. Deza, M.
Deza
and
V.P. Grishukhin.
Embeddings
of
fullerenes, virus cap-
sids, geodesic domes
and
coordinations
polyhedra
into half-cubes. Technical Re-
port
DMA
RO
960701, Ecole
Poly
technique
Federale
de
Lausanne,
Departement
de
Mathematiques,
1996. [325,329]
[1960]
M.E.
Tylkin
(=M.
Deza).
On
Ramming
geometry
of
unitary
cubes (in
Rus-
sian).
Doklady
Akademii
Nauk
SSSR
134 (1960) 1037-1040. (English
translation
in: Cybernetics and Control Theory, 134(5):
940-943,1961.)
[69,235,355,503]
[1962]
M.E.
Tylkin
(=M.
Deza). Realizability
of
distance
matrices
in
unit
cubes (in
Russian).
Problemy Kybernetiki, 7:31-42, 1962. [69,69]
[1973a]
M.
Deza.
Matrices
des formes
quadratiques
non negatives
pour
des
arguments
binaires. Comptes rendus
de
l'Academie des Sciences
de
Paris, 277(A):873-875,
1973. [54,56,405,414,450,477,503]
Bibliography
559
[1973bJ M. Deza. Une
propriete
extremale
des
plans
projectifs finis
dans
une classe de
codes equidistants. Discrete Mathematics, 6:343-352, 1973. [337,345]
[1974]
M. Deza. Solution
d'un
probleme de Erdos-Lovasz. Journal
of
Combinatorial
Theory B,
16:166-167,1974.
[345J
[1982J
M. Deza. Small
pentagonal
spaces. Rendiconti del Seminario Matematico
di
Brescia, 7:269-282, 1982.
[355J
[1978J
M. Deza, P.
Erdos,
and
P. Frankl. Intersection properties
of
systems of finite
sets. Proceedings
of
the London Mathematical Society, 3:369-384, 1978.
[340J
[1993]
M. Deza,
K.
Fukuda,
and
M.
Laurent.
The
inequicut cone. Discrete Mathematics,
119:21-48, 1993. [399,506,507J
[1993J
M.
Deza
and
V.P. Grishukhin.
Hypermetric
graphs. The Quarterly Journal
of
Mathematics Oxford, 2:399-433, 1993. [172,198,210,211,212, 262,264,269J
[1994] M.
Deza
and
V.P. Grishukhin.
Lattice
points
of
cut
cones. Combinatorics,
Probability and Computing, 3:191-214, 1994. [97,100,388J
[1995aJ M.
Deza
and
V.P. Grishukhin.
L-polytopes
and
equiangular lines. Discrete
Applied Mathematics, 56:181-214,1995.
[238J
[1995b] M.
Deza
and
V.P. Grishukhin. Delaunay polytopes
of
cut
lattices.
Linear
Algebra
and
its Applications, 226:667-686, 1995.
[181J
[1996aJ M.
Deza
and
V.P. Grishukhin.
Cut
lattices
and
equiangular lines. European
Journal
of
Combinatorics, 17:143-156,1996. [237,385J
[1996b] M.
Deza
and
V.P. Grishukhin.
Bounds
on
the
covering radius
of
a lattice.
M athematika, 43: 159-164, 1996.
[214J
[1996cJ
M.
Deza
and
V.P. Grishukhin. A zoo
of
ii-embeddable
polytopal
graphs.
Preprint
96-006, Universitat Bielefeld, 1996. [325,329J
[1991] M. Deza, V.P. Grishukhin,
and
M.
Laurent.
The
symmetries
of
the
cut
polytope
and
of
some relatives. In P.
Gritzmann
and
B. Sturmfels, editors, Applied Geometry
and
Discrete Mathematics - The Victor Klee Festschrift, volume 4
of
DIMACS
Series
in
Discrete Mathematics and Theoretical Computer Science, pages 205-220,
1991. [408,409,410J
[1992J
M. Deza, V.P. Grishukhin,
and
M.
Laurent.
Extreme
hypermetrics
and
L-
polytopes.
In
G. Halasz et al., editor, Sets, Graphs and Numbers, Budapest (Hun-
gary), 1991, volume
60
of Colloquia Mathematica Societatis Janos Bolyai, pages
157-209, 1992. [172,184,217,222,230,236,240,243,244,245]
[1993]
M. Deza, V.P. Grishukhin,
and
M.
Laurent.
The
hypermetric
cone
is
polyhedral.
Combinatorica, 13:397-411, 1993. [172,190,199]
[1995]
M. Deza, V.P. Grishukhin,
and
M.
Laurent.
Hypermetrics in geometry of num-
bers.
In
W. Cook,
L.
Lovasz,
and
P.D. Seymour, editors, Combinatorial Opti-
mization, volume 20
of
DIMACS
Series
in
Discrete Mathematics and Theoretical
Computer
Science, pages 1-109. American
Mathematical
Society, 1995. [vi,l72]
[1991]
M. Deza, M. Grotschel,
and
M.
Laurent.
Complete descriptions of small multi-
cut
polytopes.
In
P.
Gritzmann
and
B. Sturmfels, editors, Applied Geometry and
Discrete Mathematics - The Victor Klee Festschrift, volume 4 of
DIMACS
Series
in
Discrete Mathematics and Theoretical Computer Science, pages 221-252, 1991.
[400]
[1992J
M. Deza, M. Grotschel,
and
M.
Laurent.
Clique-web facets for
multicut
polytopes.
Mathematics
of
Operations Research, 17:981-1000, 1992. [400,412,465,476,481]