Hypercube embedding of generalized bipartite metrics

DOI10.1016/0166-218X(94)00087-TzbMath0821.05017OpenAlexW2072192166MaRDI QIDQ1842652

Monique Laurent, Michel Marie Deza

Publication date: 3 October 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00087-t

zbMATH Keywords

hypercubepolynomial time algorithmHamming distanceNP-completebipartite metrics\(h\)-embeddability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Related Items

Application of cut polyhedra. I, Bayes factors and the geometry of discrete hierarchical loglinear models

Cites Work

• Une propriété extremale des plans projectifs finis dans une classe de codes équidistants
• Facets for the cut cone. I
• Distance-preserving subgraphs of hypercubes
• Metrics and undirected cuts
• Recognizing Intersection Patterns
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Intersection Properties of Systems of Finite Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item