Application of cut polyhedra. I

DOI10.1016/0377-0427(94)90020-5zbMATH Open0826.52012OpenAlexW1986175898MaRDI QIDQ1891019FDOQ1891019

Authors: Monique Laurent, Michel Deza 

Publication date: 28 May 1995

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-0427(94)90020-5

Recommendations

• Applications of cut polyhedra. II
• scientific article; zbMATH DE number 718853
• Geometry of cuts and metrics
• On the cut polytope
• Computations of metric/cut polyhedra and their relatives

zbMATH Keywords

hypermetric\(\ell_ 1\)-metriccut polyhedragraphic metric

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Gale and other diagrams (52B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Metric spaces and completely monontone functions
• Title not available (Why is that?)
• HYPERMETRIC GRAPHS
• Title not available (Why is that?)
• On the Addressing Problem for Loop Switching
• Sur les inégalités valides dans \(L^ 1\)
• Extension operations for cuts
• Applications of cut polyhedra. II
• A counterexample to Borsuk’s conjecture
• Recognition of Tree Metrics
• A Review of Hierarchical Classification
• Title not available (Why is that?)
• Characterizations of derived graphs
• Metric Spaces and Positive Definite Functions
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• On the cut polytope
• Antipodal graphs and oriented matroids
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Distance-preserving subgraphs of hypercubes
• On Isometric Embeddings of Graphs
• Collapse of the metric hierarchy for bipartite graphs
• On a facet of the balanced subgraph polytope
• Clique-Web Facets for Multicut Polytopes
• On cuts and matchings in planar graphs
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• On scale embeddings of graphs into hypercubes
• The equipartition polytope. I: Formulations, dimension and basic facets
• Title not available (Why is that?)
• The max-cut problem on graphs not contractible to \(K_ 5\)
• The cut polytope and the Boolean quadric polytope
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Correlation polytopes: Their geometry and complexity
• On the cycle polytope of a binary matroid
• The cone of distance matrices
• Zonoid theory and Hilbert's fourth problem
• \(\ell_ 1\)-rigid graphs
• Hypermetric Spaces and the Hamming Cone
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• Addresses for graphs
• Title not available (Why is that?)
• Some new classes of facets for the equicut polytope
• The equipartition polytope. II: Valid inequalities and facets
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• The inequicut cone
• Lifting facets of the cut polytope
• Title not available (Why is that?)
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Combinatorial approaches to multiflow problems
• The hypermetric cone is polyhedral
• A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
• Max-cut in circulant graphs
• Hypercube embedding of generalized bipartite metrics
• The structure of distances in networks
• Title not available (Why is that?)
• On the Extreme Rays of the Metric Cone
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• Title not available (Why is that?)
• The classification of finite connected hypermetric spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• The cut cone. III: On the role of triangle facets
• The even and odd cut polytopes
• Graphic vertices of the metric polytope
• The relation between hierarchical and Euclidean models for psychological distances
• An ``average distance inequality for large subsets of the cube
• Title not available (Why is that?)
• Extremal Metrics Induced by Graphs
• Collapsing and lifting for the cut cone
• Title not available (Why is that?)
• Computing extreme rays of the metric cone for seven points
• All the facets of the six-point Hamming cone
• The CW-inequalities for vectors in \(\ell_ 1\)
• Title not available (Why is that?)
• Embeddings of Ultrametric Spaces in Finite Dimensional Structures
• L-polytopes and equiangular lines
• Title not available (Why is that?)
• Title not available (Why is that?)
• A generalized cut-condition for multiflows in matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (16)

• A dynamic inequality generation scheme for polynomial programming
• Learning representations from dendrograms
• Mathematical programming models and exact algorithms
• Algebraic and numerical techniques for the computation of matrix determinants
• Applications of cut polyhedra. II
• New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities
• Improved compact formulations for metric and cut polyhedra
• Generating facets for the cut polytope of a graph by triangular elimination
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Cycle algebras and polytopes of matroids
• Generating cutting planes for the semidefinite relaxation of quadratic programs
• Maximum cut parameterized by crossing number
• Classes of cut ideals and their Betti numbers
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Seminormality, canonical modules, and regularity of cut polytopes
• Monotone maps, sphericity and bounded second eigenvalue

This page was built for publication: Application of cut polyhedra. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1891019)