Recognizing halved cubes in a constant time per edge

Wilfried Imrich; Sandi Klavžar; Aleksander Vesel

doi:10.1016/0195-6698(95)90042-X

Recognizing halved cubes in a constant time per edge

Wilfried Imrich, Sandi Klavžar, Aleksander Vesel

Chair of Applied Mathematics (170)

Universität Maribor

Research output: Contribution to journal › Article › Research › peer-review

Abstract

Graphs that can be isometrically embedded into the metric space l1 are called l1-graphs. Halved cubes play an important role in the characterization of l1-graphs. We present an algorithm that recognizes halved cubes in O(n log2 n) time.

Original language	English
Pages (from-to)	617-621
Number of pages	5
Journal	European journal of combinatorics
Volume	16.1995
Issue number	6
DOIs	https://doi.org/10.1016/0195-6698(95)90042-X
Publication status	Published - 29 Jul 1995

Access to Document

10.1016/0195-6698(95)90042-X

Cite this

@article{000707cd6d0a4222b22a384f859bced6,

title = "Recognizing halved cubes in a constant time per edge",

abstract = "Graphs that can be isometrically embedded into the metric space l1 are called l1-graphs. Halved cubes play an important role in the characterization of l1-graphs. We present an algorithm that recognizes halved cubes in O(n log2 n) time.",

author = "Wilfried Imrich and Sandi Klav{\v z}ar and Aleksander Vesel",

year = "1995",

month = jul,

day = "29",

doi = "10.1016/0195-6698(95)90042-X",

language = "English",

volume = "16.1995",

pages = "617--621",

journal = "European journal of combinatorics ",

issn = "0195-6698",

publisher = "Academic Press",

number = "6",

}

TY - JOUR

T1 - Recognizing halved cubes in a constant time per edge

AU - Imrich, Wilfried

AU - Klavžar, Sandi

AU - Vesel, Aleksander

PY - 1995/7/29

Y1 - 1995/7/29

N2 - Graphs that can be isometrically embedded into the metric space l1 are called l1-graphs. Halved cubes play an important role in the characterization of l1-graphs. We present an algorithm that recognizes halved cubes in O(n log2 n) time.

AB - Graphs that can be isometrically embedded into the metric space l1 are called l1-graphs. Halved cubes play an important role in the characterization of l1-graphs. We present an algorithm that recognizes halved cubes in O(n log2 n) time.

UR - http://www.scopus.com/inward/record.url?scp=58149210792&partnerID=8YFLogxK

U2 - 10.1016/0195-6698(95)90042-X

DO - 10.1016/0195-6698(95)90042-X

M3 - Article

AN - SCOPUS:58149210792

SN - 0195-6698

VL - 16.1995

SP - 617

EP - 621

JO - European journal of combinatorics

JF - European journal of combinatorics

IS - 6

ER -

Recognizing halved cubes in a constant time per edge

Abstract

Access to Document

Other files and links

Cite this