Home Research - CB Problem | November 30, 2022 |

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.

. The first test-suite includes 85 standard graphs with known optimal solutions that belong to seven different families (3__Standard graphs__*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. Some of these graphs were originally used by Romero-Monsivais__this file__*et al.*in [2] to evaluate a branch & bound algorithm for the CB problem.. The second set contains 28 problem instances with a number of vertices between 9 and 715, coming directly from the__Harwell-Boeing graphs__. 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__Harwell-Boeing Sparse Matrix Collection__*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].

__Iterated Three-Phase Search algorithm for the CB problem (ITPS).__

Please cite as:

Jintong Ren, Jin-Kao Hao and Eduardo Rodriguez-Tello.Submitted to IEEE Access April 30, 2019.__An Iterated Three-Phase Search Approach for Solving the Cyclic Bandwidth Problem,__

__Tabu Search for the CB problem (TScb).__

Please cite as:

Eduardo Rodriguez-Tello, Hillel Romero-Monsivais, Gabriel Ramírez-Torres and Frédéric Lardeux., Computers & Operations Research, 57:17-32, DOI: 10.1016/j.cor.2014.11.013, Elsevier May 2015.__Tabu Search for the Cyclic Bandwidth Problem,__

. 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.__Best Known Solutions__

- J. Leung, O. Vornberger, J. Witthoff, On some variants of the bandwidth minimization problem, SIAM Journal on Computing 13(3)(1984) 650-667.
- 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.
- 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.
- 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