Eduardo Rodriguez-Tello - Research - Cyclic Bandwidth Sum Problem

Cyclic Bandwidth Sum (CBS) Problem

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. Dynamic multi-armed bandit algorithm for the cyclic bandwidth sum problem,, IEEE Access, 7(1):40258-40270, DOI: 10.1109/ACCESS.2019.2906840, IEEE Press, March 2019.

Memetic algorithm for the CBS problem (MA).
Please cite as:
Eduardo Rodriguez-Tello, Valentina Narvaez-Teran and Frédéric Lardeux. Comparative study of different memetic algorithm configurations for the cyclic bandwidth sum problem,, 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.

Benchmark Instances

Computational Results

References

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.

Main menu