ALCOMFT-TR-01-114

Dimitrios M. Thilikos, Maria J. Serna and Hans L. Bodlaender
A constructive linear time algorithm for small cutwidth
Barcelona and Utrecht. Work package 4. May 2001.

Abstract: The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a linear layout [v₁,...,v_n] in such a way that for every i=1,...,n-1, there are at most k edges with the one endpoint in {v₁,...,v_i} and the other in {v_i+1,...,v_n}. In this paper we show how to construct, for any constant k, a linear time algorithm that for any input graph G, answers whether G has cutwidth at most k and, in the case of a positive answer, outputs the corresponding linear layout.

Postscript file: ALCOMFT-TR-01-114.ps.gz (149 kb).