Square-root rule of two-dimensional bandwidth problem
Lan Lin, Yixun Lin (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an × grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...