Authors : Mochamad Suyudi, Mustafa Mamat, Sukono and Sudradjat Supian
Abstract: The cutwidth minimization problem consists of finding a linear layout of a graph so that, the maximum linear cut of edges (i.e., the number of edges that cut a line between consecutive vertices) is minimized. This study, starts by reviewing previous exact approaches for special classes of graphs as well as a linear integer formulation for the general problem. We propose a branch and bound algorithm based on different lower bounds on the cutwidth of partial solutions.
Mochamad Suyudi, Mustafa Mamat, Sukono and Sudradjat Supian, 2017. Branch and Bound for the Cutwidth Minimization Problem. Journal of Engineering and Applied Sciences, 12: 5684-5689.