English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Routing through a Rectangle

Mehlhorn, K., & Preparata, F. P. (1986). Routing through a Rectangle. Journal of the ACM, 33, 60-85.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AEC5-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AEC6-8
Genre: Journal Article

Files

show Files
hide Files
:
Mehlhorn_a_1986_n.pdf (Any fulltext), 2MB
 
File Permalink:
-
Name:
Mehlhorn_a_1986_n.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Mehlhorn, Kurt1, Author           
Preparata, F. P.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Content

show
hide
Free keywords: -
 Abstract: In this paper an O(N log N) algorithm for routing through a rectangle is presented. Consider an n-by-m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in O(N log N) time; this contrasts favorably with the area of the layout that might be as large as N2. The layout constructed can be wired using four layers of interconnect with only O(N) contact cuts. A partial extension to multiterminal nets is also discussed.

Details

show
hide
Language(s): eng - English
 Dates: 2008-03-061986
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 344588
Other: Local-ID: C1256428004B93B8-B787798F060A30DFC1257149004A7466-JACM::MehlhornP1986
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Journal of the ACM
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 33 Sequence Number: - Start / End Page: 60 - 85 Identifier: -