Home Research - CBS Problem October 03, 2023   

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 Cn, 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
Benchmark Instances

Computational Results

  1. J. Yuan, Cyclic arrangement of graphs, Graph Theory Notes of New York, New York Academy of Sciences (1995) 6-10.
  2. S. N. Bhatt, F. T. Leighton, A framework for solving VLSI graph layout problems, Journal of Computer and System Sciences 28 (1984) 300-343.
  3. J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984.
  4. L. Harper, Optimal assignment of numbers to vertices, Journal of SIAM 12 (1964) 131-135.
  5. B. Monien, I. H. Sudborough, Embedding one interconnection network in another, Computational Graph Theory, Computing Supplementum 7 (1990) 257-282.
  6. 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