Recognition of thel1-Graphs with ComplexityO(nm), orFootball in a Hypercube

AbstractWe fill in the details of the algorithm sketched in [6] and determine its complexity. As a 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 non-l1-graph allowing a highly isometric embedding into a halved cube