Algorithm for embedding a class of non-even routing problems in even routing problems

Dee Parks, Miroslaw Truszczynski

Research output: Contribution to conferencePaperpeer-review

Abstract

In this paper we present part of a complete solution of a two-terminal net routing problem for certain non-convex grids without holes that we call channel graphs. We present an algorithm for embedding a non-even channel graph routing problem in an even channel graph routing problem. We refer to the algorithm as EMBED. EMBED runs in time O(b), where b is the number of vertices on the boundary, and is similar to an algorithm described by Becker and Mehlhorn for planar graphs. Due to the restrictions we place on the shape of channel graph routing problems, however, we are able to obtain a lower complexity for our algorithm than that of the Becker and Mehlhorn algorithm. Their algorithm has complexity O(bn), where n is the number of vertices in the graph.

Original languageEnglish
Pages152-158
Number of pages7
StatePublished - 1991
EventProceedings of the Second Great Lakes Symposium on VLSI - Kalamazoo, MI, USA
Duration: Feb 28 1992Feb 29 1992

Conference

ConferenceProceedings of the Second Great Lakes Symposium on VLSI
CityKalamazoo, MI, USA
Period2/28/922/29/92

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Algorithm for embedding a class of non-even routing problems in even routing problems'. Together they form a unique fingerprint.

Cite this