Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube (Q1911847)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube |
scientific article |
Statements
Recognition of the \(\ell_ 1\)-graphs with complexity \(O(nm)\), or Football in a hypercube (English)
0 references
13 January 1997
0 references
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.
0 references
hypercube
0 references
algorithm
0 references
complexity
0 references
highly isometric embedding
0 references
halved cube
0 references