Search
Now showing items 1-10 of 11
Planar Embedding of Planar Graphs
(1983-02)
Planar embedding with minimal area of graphs on an integer grid is an interesting problem in VLSI theory. Valiant [V] gave an algorithm to construct a planar embedding for trees in linear area; he also proved that there ...
An Approximation Algorithm for Manhattan Routing
(1983-02)
Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call flux. We show that flux, like density, is a ...
A Framework for Solving VSLI Graph Layout Problems
(1983-10)
This paper introduces a new divide-and-conquer framework for VLSI graph layout. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework ...
Probabilistic Searching in Sorted Linked Lists
(1983-11)
Janko [2] and Bentley, Stanat, and Steele [1] have described probabilistic procedures for data manipulation in sorted linnked lists. Their procedures are based on an algorithm which performs a Member search operation using ...
Wafer-scale Integration of Systolic Arrays
(1983-02)
VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an entire system (or network ...
Layouts for the Shuffle-exchange Graph and Lower Bound Techniques for VLSI
(1982-08)
The thesis is divided into two parts. In the first part, we describe and analyze several new VLSI layouts for the shuffle-exchange graph. These include:1) an asymptotically optimal, (N /log N)-area layout for the ...
Layouts for the Suffle-Exchange Graph Based on the Complex Plane Diagram
(1982-06)
The shuffule-exchange graph is one of the best structures known for parallel computation. Among other things, a shuffle-exchange computer can be used to compute discrete. Fourier transforms, multiply matrices, evaluate ...
An Asymptotically Optimal Layout for the Shuffle-exchange Graph
(1982-10)
The shuffle-exchange graph is one of the best structures known for parallel computation. Among other things, a shuffle-exchange computer can be used to compute discrete Fourier transforms, multiply matrices, evaluate ...
The Markov Chain Tree Theorem
(1983-11)
Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight ...