Geometry of Cuts and Metrics
Cuts and metrics are well-known objects that arise - independently, but with many deep and fascinating connections - in diverse fields: in graph theory, combinatorial optimization, geometry of numbers, distance geometry, combinatorial matrix theory, statistical physics, VLSI design etc. A main featu...
| Main Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1997, 1997
|
| Edition: | 1st ed. 1997 |
| Series: | Algorithms and Combinatorics
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Outline of the Book
- I.Measure Aspects: El-Embeddability and Probability
- Preliminaries on Distances
- The Cut Cone and #x2113;-Metrics
- The Correlation Cone and {0. 1}-Covariances
- Conditions for -Embeddability
- Operations
- -Metrics from Lattices, Semigroups and Normed Spaces
- Metric Transforms of -Spaces
- Lipschitz Embeddings
- Dimensionality Questions for -Embeddings
- Examples of the Use of the -Metric
- Basic Definitions
- I1.Hypermetric Spaces: an Approach via Geometry of Numbers
- Preliminaries on Lattices
- Hypermetrics and Delaunay Polytopes
- Delaunay Polytopes: Rank and Hypermetric Faces
- Extreme Delaunay Polytopes
- Hypermetric Graphs
- I11.Isometric Embeddings of Graphs
- Preliminaries on Graphs
- Isometric Embeddings of Graphs into Hypercubes
- Isometric Embeddings of Graphs into Cartesian Products
- -Graphs
- IV.Hypercube Embeddings and Designs
- Rigidity of the Equidistant Metric
- Hypercube Embeddings of the Equidistant Metric
- Recognition of Hypercube Embeddable Metrics
- Cut Lattices, Quasi -Distances and Hilbert Bases
- V.Facets of the Cut Cone and Polytope
- Operations on Valid Inequalities and Facets
- Triangle Inequalities
- Hypermetric Inequalities
- Clique-Web Inequalities
- Other Valid Inequalities and Facets
- Geometric Properties