Home Research - CBS Problem | October 03, 2023 |

The *Cyclic Bandwidth Sum* (CBS) problem for graphs is a well-studied combinatorial optimization problem whose main objective is to embed a *n*-vertex undirected and unweighted graph into the cycle *C _{n}*, such that the sum of (cyclic) difference of labels of adjacent vertices is minimized. It was first studied by Yuan in 1995 who demonstrated that it is a NP-hard problem [1]. This problem arises in some important application areas like VLSI designs [2,3], code design [4], simulation of interconnection networks for parallel computer systems [5] and scheduling in broadcasting based networks [6].

Source Codes

__Dynamic multi-armed bandit algorithm for the CBS problem (DMAB+MA).__

Please cite as:

Eduardo Rodriguez-Tello, Valentina Narvaez-Teran and Frédéric Lardeux., IEEE Access, 7(1):40258-40270, DOI: 10.1109/ACCESS.2019.2906840, IEEE Press, March 2019.__Dynamic multi-armed bandit algorithm for the cyclic bandwidth sum problem,____Memetic algorithm for the CBS problem (MA).__

Please cite as:

Eduardo Rodriguez-Tello, Valentina Narvaez-Teran and Frédéric Lardeux., Proceedings of the PPSN 2018, Coimbra, Portugal, Lecture Notes in Computer Science, 11101:82-94, DOI: 10.1007/978-3-319-99253-2_7, Springer 2018.__Comparative study of different memetic algorithm configurations for the cyclic bandwidth sum problem,__

- J. Yuan, Cyclic arrangement of graphs, Graph Theory Notes of New York, New York Academy of Sciences (1995) 6-10.
- S. N. Bhatt, F. T. Leighton, A framework for solving VLSI graph layout problems, Journal of Computer and System Sciences 28 (1984) 300-343.
- J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984.
- L. Harper, Optimal assignment of numbers to vertices, Journal of SIAM 12 (1964) 131-135.
- B. Monien, I. H. Sudborough, Embedding one interconnection network in another, Computational Graph Theory, Computing Supplementum 7 (1990) 257-282.
- V. Liberatore, Multicast scheduling for list requests, in: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, volume 2, IEEE, 2002, pp. 1129-1137 vol.2.

® 2008 Eduardo Rodriguez-Tello