Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2021) | last year (2020) | two years ago (2019) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Mehlhorn, Kurt
Preparata, F. P.		dblp
dblp

BibTeX cite key*:

JACM::MehlhornP1986

Title

Title*:

Routing through a Rectangle


Mehlhorn_a_1986_n.pdf (1708.82 KB)

Journal

Journal Title*:

Journal of the ACM
Journal's URL:


Download URL
for the article:

http://delivery.acm.org/10.1145/10000/4994/p60-mehlhorn.pdf?key1=4994&key2=4485613611&coll=GUIDE&dl=GUIDE&CFID=5761340&CFTOKEN=76401576
Language:

English

Publisher

Publisher's
Name:

ACM
Publisher's URL:


Publisher's
Address:

New York, NY, USA
ISSN:


Vol, No, pp, Date

Volume*:

33
Number:

1

Publishing Date:

1986

Pages*:

60-85
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

Categories and Subject Descriptors: B.7. I [Integrated Circuits]: Types and Design Styles- VLSI (very large scale integration), B.7.2 [Integrated Circuits]: Design Aids-placement and routing, E. I [Data]:
Data Structures--arrays, trees, F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-routing and layout

General Terms: Design, Theory

HyperLinks / References / URLs:

http://portal.acm.org/citation.cfm?doid=4904.4994

Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{JACM::MehlhornP1986,
AUTHOR = {Mehlhorn, Kurt and Preparata, F. P.},
 TITLE = {Routing through a Rectangle},
 JOURNAL = {Journal of the ACM},
 PUBLISHER = {ACM},
 YEAR = {1986},
 NUMBER = {1},
 VOLUME = {33},
 PAGES = {60--85},
 ADDRESS = {New York, NY, USA},
}

Entry last modified by Anja Becker, 03/06/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel		Created
04/07/2006 03:33:14 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Uwe Brahm
Uwe Brahm		Edit Dates
06.03.2008 08:57:30
10.11.2006 15:15:32
10.11.2006 14:42:46
08-04-2006 18:09:06
07.04.2006 15:34:43
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_1986_n.pdf