| Issue |
RAIRO-Theor. Inf. Appl.
Volume 45, Number 4, October-December 2011
|
|
|---|---|---|
| Page(s) | 399 - 411 | |
| DOI | https://doi.org/10.1051/ita/2011120 | |
| Published online | 22 September 2011 | |
Square-root rule of two-dimensional bandwidth problem∗
1 School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China
2 The Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education, Guilin University of Electronic Technology, Guilin 541004, P.R. China
3 Department of Mathematics, Zhengzhou University, Zhengzhou 450052, P.R. China
linyixun@zzu.edu.cn
Received: 26 February 2011
Accepted: 2 August 2011
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs.
Mathematics Subject Classification: 05C78 / 68R10
Key words: Network layout / two-dimensional bandwidth / lower and upper bounds / optimal embedding.
© EDP Sciences 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.