Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
Moon-Jung Chung, Fillia S. Makedon, Ivan Hal Sudborough, Jonathan Turner · SIAM Journal on Computing · 1985
Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in $O(n(\log n)^{d - 2} )$ steps. This has applications to integrated circuit layout, in particular the layout of Weinberger arrays [41]. This also yields an algorithm for determining the black/white pebble demand of degree three trees. We also show that for degree three trees, cutwidth is identical to search number and give a forbidden subgraph characterization of degree three trees having cutwidth k.