New Lower Bound Techniques for VLSI.

Abstract

In this paper, crossing number and wire area arguments are used to find lower bounds on the layout area and maximum edge length of a variety of new and computationally useful networks. In particular, an N-node planar graph which has layout are theta(N log N) and maximum edge length theta(N(1/2)/log(1/2)N), an N-node graph with an theta(x 1/2)-separator which has layout area theta(N log(2)N) and maximum edge length theta(N(1/2)logN/loglogN), and an N-node graph with an theta(x(1-1/r)-separator which has maximum edge length theta(N(1-1/r) for any r > or = .3.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1982
Accession Number
ADA121513

Entities

People

  • Frank Thomson Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Computations
  • Computer Science
  • Computers
  • Crossings
  • Differential Equations
  • Embedding
  • Large Scale Integration
  • Massachusetts
  • Mathematics
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Separators
  • Three Dimensional
  • Trees (Data Structures)
  • Two Dimensional
  • Very Large Scale Integration

Readers

  • Graph Algorithms and Convex Optimization.