A 2d - 1 Lower Bound 2-Layer Knock-Knee Channel Routing

Abstract

In this paper, we describe a 2-point net channel routing problem with density d that requires channel width 2d - 1 in the 2-layer knock-knee channel routing model. This means that the (2d - 1)-track algorithms of Rivest, Baratz and Miller, Bolognesi and Brown, Frank, Mehlhorn, Preparata and Sarrafzadeh and Berger, Brady, Brown and Leigton are, in some cases, optimal. Thus any improvement of these algorithms must rely on problem features other than density (such as flux), or must make fundamental changes in the wiring model (such as increasing the number of layers or allowing wires to overlap.)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1989
Accession Number
ADA211948

Entities

People

  • Tom Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Circuit Boards
  • Circuits
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Crossings
  • Governments
  • Integrated Circuits
  • Massachusetts
  • Mathematics
  • Plastic Explosives
  • Sequences
  • Terminals

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Military History