On Routing Two-Terminals Nets in the Presence of Obstacles

Abstract

We consider the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard twolayer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. Our main results are polynomial time algorithms to determine whether the given nets are routable in either model for any fixed k. We introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size is propotional to the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA452097

Entities

People

  • Joseph Jaja
  • S. A. Wu

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Contracts
  • Electrical Engineering
  • Engineering
  • Heuristic Methods
  • Information Operations
  • Instructions
  • Maryland
  • Mathematics
  • Monitoring
  • Standards
  • Terminals
  • Universities

Fields of Study

  • Mathematics

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.