论文部分内容阅读
The cutwidth problem for a graph G is to embed G into a path Pn such that the maximum number of overlap edges (i. e. , the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.