Home Research - CB Problem November 30, 2022

Cyclic Bandwidth (CB) Problem

The Cyclic Bandwidth problem (CB) is a graph embedding problem. It was first stated by Leung et al. in 1984 in relation with the design of a ring interconnection network [1]. Their aim was to find an arrangement on a cycle for a set V of computers with a known communication pattern, given by the graph G(V,E), in such a way that every message sent can arrive at its destination in at most k steps. The CB problem arises also in other important application areas like VLSI designs, data structure representations, code design and interconnection networks for parallel computer systems.

Benchmark Instances
• Standard graphs. The first test-suite includes 85 standard graphs with known optimal solutions that belong to seven different families (3 r-dimensional hypercubes, 10 three dimensional meshes, 12 complete r level k-ary trees, and 15 graphs from each of the following classes: paths, cycles, two dimensional meshes and caterpillars). This set of benchmark instances is composed of 23 small graphs (n < 100), 24 medium graphs (100 < n ≤ 200) and 38 large graphs (200 < n ≤ 8192). A brief description of each selected class of graph and its corresponding optimal cyclic bandwidth value are summarized in this file. Some of these graphs were originally used by Romero-Monsivais et al. in [2] to evaluate a branch & bound algorithm for the CB problem.

• Harwell-Boeing graphs. The second set contains 28 problem instances with a number of vertices between 9 and 715, coming directly from the Harwell-Boeing Sparse Matrix Collection. This collection gathers standard test matrices arising from a wide variety of scientific and engineering practical problems which can be considered as adjacency matrices in order to construct graphs. Most of the graphs in this second set (24 of them) were previously used by Duarte et al. [3] and Lozano et al. [4] as benchmarks instances for the antibandwidth problem [1]. The rest of the instances (4 graphs) were collected by us to complement this set with small graphs (n ≤ 24) that can be solved exactly using the branch & bound algorithm proposed in [2].
Source Codes
Computational Results
• Best Known Solutions. As far as we know this file contains the best-known solutions for this problem to date (06/06/2019). Most of these solutions were obtained using the Iterated Three-Phase Search (ITPS) algorithm. However, a reduced number of best-known solutions are still produced by our Tabu Search algorithm.
References
1. J. Leung, O. Vornberger, J. Witthoff, On some variants of the bandwidth minimization problem, SIAM Journal on Computing 13(3)(1984) 650-667.
2. H. Romero-Monsivais, E. Rodriguez-Tello and G. Ramírez, A new branch and bound algorithm for the cyclic bandwidth problem, Lecture Notes in Artificial Intelligence 7630(2012) 139-150.
3. A. Duarte, R. Martí, M. G. C. Resende, R. M. A. Silva, Grasp with path relinking heuristics for the antibandwidth problem, Networks 58(3)(2011) 171-189.
4. M. Lozano, A. Duarte, F. Gortázar, R. Martí, Variable neighborhood search with ejection chains for the antibandwidth problem, Journal of Heuristics 18(6)(2012) 919-938.

® 2008 Eduardo Rodriguez-Tello