Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube
type: Item
instance of: scholarly article
title: Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube
zbMATH Open document ID: 0854.05093
published in: European Journal of Combinatorics
publication date: 1997-01-13T00:00:00Z
review text: Adapted from the authors' introduction: We fill in the details of the algorithm sketched in the second author's paper [On scale embeddings of graphs into hypercubes, Eur. J. Comb. 14, No. 2, 117-130 (1993; Zbl 0773.05044)], and determine its complexity. As part of this main algorithm, we also describe an algorithm which recognizes graphs which are isometric subgraphs of halved cubes. We discuss possible further applications of the same ideas and give a nice example of a non-\(\ell_1\)-graph allowing a highly isometric embedding into a halved cube.
reviewed by: M.Marx
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 871022
zbMATH Keywords: hypercube
zbMATH Keywords: algorithm
zbMATH Keywords: complexity
zbMATH Keywords: highly isometric embedding
zbMATH Keywords: halved cube
author: Michel Deza
author: S. Shpectorov
MaRDI profile type: Publication
full work available at URL: eujc.1996.0024
OpenAlex ID: W1528683952
DOI: 10.1006/EUJC.1996.0024
description: scientific article; zbMATH DE number 871022