Recognizing Hamming graphs in linear time and space

Wilfried Imrich; Sandi Klavžr

doi:10.1016/s0020-0190(97)00095-1

Recognizing Hamming graphs in linear time and space

Wilfried Imrich
, Sandi Klavžr

Chair of Applied Mathematics (170)

Universität Maribor

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

6 Citations (Scopus)

Abstract

Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.

Original language	English
Pages (from-to)	91-95
Number of pages	5
Journal	Information processing letters
Volume	63.1997
Issue number	2
DOIs	https://doi.org/10.1016/s0020-0190(97)00095-1
Publication status	Published - 28 Jul 1997

Keywords

Analysis of algorithms
Design of algorithms
Hamming graphs

Access to Document

10.1016/s0020-0190(97)00095-1

Cite this

@article{978ae591381340b0880c35ef5b1d30f5,

title = "Recognizing Hamming graphs in linear time and space",

abstract = "Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.",

keywords = "Analysis of algorithms, Design of algorithms, Hamming graphs",

author = "Wilfried Imrich and Sandi Klav{\v z}r",

year = "1997",

month = jul,

day = "28",

doi = "10.1016/s0020-0190(97)00095-1",

language = "English",

volume = "63.1997",

pages = "91--95",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Recognizing Hamming graphs in linear time and space

AU - Imrich, Wilfried

AU - Klavžr, Sandi

PY - 1997/7/28

Y1 - 1997/7/28

N2 - Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.

AB - Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.

KW - Analysis of algorithms

KW - Design of algorithms

KW - Hamming graphs

UR - https://www.scopus.com/pages/publications/24144501848

U2 - 10.1016/s0020-0190(97)00095-1

DO - 10.1016/s0020-0190(97)00095-1

M3 - Article

AN - SCOPUS:24144501848

SN - 0020-0190

VL - 63.1997

SP - 91

EP - 95

JO - Information processing letters

JF - Information processing letters

IS - 2

ER -

Recognizing Hamming graphs in linear time and space

Abstract

Keywords

Access to Document

Other files and links

Cite this