MPI-INF D1 Publications: Journal Article: Routing through a Rectangle

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

Mehlhorn, Kurt
Preparata, F. P.

dblp
dblp

BibTeX cite key*:

JACM::MehlhornP1986

Title

Title*:	Routing through a Rectangle
Attachment(s):	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

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

Attachment Section

View attachments here:

Mehlhorn_a_1986_n.pdf