ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Efficient breakout routing in printed circuit boards
Full text PdfPdf (599 KB)
Source Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents
Nice, France
Pages: 460 - 462  
Year of Publication: 1997
ISBN:0-89791-878-9
Authors
John Hershberger  Mentor Graphics, 1001 Ridder Park Drive, San Jose, CA
Subhash Suri  Department of Computer Science, Washington University, St. Louis, MO
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 15,   Citation Count: 4
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.263082
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
Wun-Tat Chan , Francis Y. L. Chin, Efficient algorithms for finding disjoint paths in grids, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.454-463, January 05-07, 1997, New Orleans, Louisiana, United States
 
2
Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
3
Wayne Wei-Ming Dai , Raymond Kong , Masao Sato, Routability of a rubber-band sketch, Proceedings of the 28th conference on ACM/IEEE design automation, p.45-48, June 17-22, 1991, San Francisco, California, United States  [doi>10.1145/127601.127623]
 
4
F. Miller Malley, Single-layer wire routing and compaction, MIT Press, Cambridge, MA, 1990
 
5
V. P. Roychowdhury , Jehoshua Bruck , Thomas Kailath, Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays, IEEE Transactions on Computers, v.39 n.4, p.480-489, April 1990  [doi>10.1109/12.54841]
 
6
Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
 
7
Man-Fai Yu , Wayne Wei-Ming Dai, Single-layer fanout routing and routability analysis for Ball Grid Arrays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.581-586, November 05-09, 1995, San Jose, California, United States
 
8
Man-Fai Yu , Joel Darnauer , Wayne Wei-Ming Dai, Interchangeable pin routing with application to package layout, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.668-673, November 10-14, 1996, San Jose, California, United States

CITED BY  4
M. M. Ozdal , M. D. F. Wong , P. S. Honsinger, An escape routing framework for dense boards with high-speed design constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.759-766, November 06-10, 2005, San Jose, CA
M. M. Ozdal , M. D. F. Wong , P. S. Honsinger, Optimal routing algorithms for pin clusters in high-density multichip modules, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.767-774, November 06-10, 2005, San Jose, CA
Muhammet Mustafa Ozdal , Martin D. F. Wong , Philip S. Honsinger, Optimal routing algorithms for rectilinear pin clusters in high-density multichip modules, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-20, September 2008
Renshen Wang , Chung-Kuan Cheng, Octilinear redistributive routing in bump arrays, Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 10-12, 2009, Boston Area, MA, USA

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems


General Terms:
Algorithms, Theory

Collaborative Colleagues:
John Hershberger: colleagues
Subhash Suri: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player