NDLI: Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs

Content Provider	IEEE Xplore Digital Library
Author	Chung-Wei Lin Szu-Yu Chen Chi-Feng Li Yao-Wen Chang Chia-Lin Yang
Copyright Year	1982
Abstract	Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	643
Ending Page	653
Page Count	11
File Size	945378
File Format	PDF
ISSN	02780070
Volume Number	27
Issue Number	4
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-04-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Pins Steiner trees Manufacturing Tree graphs Heuristic algorithms Large-scale systems Computer science NP-complete problem Timing Steiner tree Physical design routing spanning tree
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithm

Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point-Based Algorithm

FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction

On the Construction of Optimal Obstacle-Avoiding Rectilinear Steiner Minimum Trees

A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem

Critical-Trunk-Based Obstacle-Avoiding Rectilinear Steiner Tree Routings and Buffer Insertion for Delay and Slack Optimization

Efficient Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Geometric Reduction

Efficient Steiner tree construction based on spanning graphs

Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs

Similar Documents

Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction Algorithm

Obstacle-Avoiding Rectilinear Steiner Tree Construction: A Steiner-Point-Based Algorithm

FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction

On the Construction of Optimal Obstacle-Avoiding Rectilinear Steiner Minimum Trees

A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem

Critical-Trunk-Based Obstacle-Avoiding Rectilinear Steiner Tree Routings and Buffer Insertion for Delay and Slack Optimization

Efficient Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Geometric Reduction

Efficient Steiner tree construction based on spanning graphs

Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs