The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph is the minimum value of the maximum number of overlap edges when is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.
The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an × grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies...
The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an × grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies...
Page 1