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
    0 references
    hypercube
    0 references
    algorithm
    0 references
    complexity
    0 references
    highly isometric embedding
    0 references
    halved cube
    0 references
    0 references
    0 references

    Identifiers