Antibandwidth and cyclic antibandwidth of meshes and hypercubes

Raspaud, A, Schroder, H, Sykora, O, Torok, L and Vrt'o, I 2009, 'Antibandwidth and cyclic antibandwidth of meshes and hypercubes', Discrete Mathematics, vol. 309, no. 11, pp. 3541-3552.


Document type: Journal Article
Collection: Journal Articles

Title Antibandwidth and cyclic antibandwidth of meshes and hypercubes
Author(s) Raspaud, A
Schroder, H
Sykora, O
Torok, L
Vrt'o, I
Year 2009
Journal name Discrete Mathematics
Volume number 309
Issue number 11
Start page 3541
End page 3552
Total pages 12
Publisher Elsevier Science Bv
Abstract The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle Cn, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth.
Subject Applied Discrete Mathematics
Keyword(s) Antibandwidth
Cyclic antibandwidth
Hypercube
Mesh
Toroidal mesh
DOI - identifier 10.1016/j.disc.2007.12.058
Copyright notice © 2008 Elsevier B.V. All rights reserved.
ISSN 0012-365X
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 26 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 32 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 168 Abstract Views  -  Detailed Statistics
Created: Wed, 17 Nov 2010, 16:09:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us