IMPROVED BOUNDS ON CUTWIDTHS OF SHUFFLE-EXCHANGE AND DE BRUIJN GRAPHS
Burkhard Monien, Imrich Vrt’o · Parallel Processing Letters · 2004
We prove that the cutwidth of the n-dimensional shuffle-exchange graph is at most ⌈2n+1/n⌉, for n≥10. This essentially improves on the previous best constant factors. As a consequence we obtain an improved upper bound for the cutwidth of the de Bruijn graph.