𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recognizing Hamming graphs in linear time and space

✍ Scribed by Wilfried Imrich; Sandi Klavžar

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
417 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

A linear time algorithm to recognize cir
A linear time algorithm to recognize circular permutation graphs
✍ Sritharan, R. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

An undirected graph G is a circular permutation graph if it can be represented by the following intersectiori model: Each vertex of G corresponds to a chord in the annular region between two concentric circles, and two vertices are adjacent in G if and only if their corresponding chords intersect ea