Document Type

Technical Report

Publication Date

1984-02-01

Filename

WUCS-84-1.pdf

Technical Report Number

WUCS-84-1

Abstract

We consider the problem of embedding one graph in another, where the cost of an embedding is the maximum distance in the target graph separating vertices that are adjacent in the source graph. An important special case, know as the bandwidth minimization problem, is when the target graph is a path. This author has shown that for random graphs having bandwidth at most k, a well-known heuristic produces solutions having cost not more than 3k with high probability. This paper considers generalizations of this heuristic and analyzes their performance in other classes of target graphs. In particular, we describe a heuristic that for random graphs having a cost k embedding in a rectangular grid, produces embeddings having cost not more than 3k with high probability. This problem has applications to laying out circuits in the plane so as to minimize the lengths of the longest wire. Similar results can be obtained for multi-dimensional grids, as well as triangular and hexagonal grids.

Comments

Permanent URL: http://dx.doi.org/10.7936/K75D8Q6B

Share

COinS