Advanced search
Publication Cover
IETE Journal of Research Volume 23, 1977 - Issue 7
Submit an article Journal homepage
1
Views
2
CrossRef citations to date
0
Altmetric
Original Articles

Automated Routing of Large-Scale Circuits

Invited Paper

N. K. BoseEE Deptt., Univ. of Pittsburgh, Pittsburgh, PA15261USA.
Pages 407-412 | Received 16 Feb 1977, Published online: 11 Jul 2015

REFERENCES

  • Breuer (M A). Recent Developments in the Automated Design and Analysis of Digital Systems. Proc. IEEE. 60, 1; 1972; 12–27.
  • Kernighan (B W) and Lin (S). An Efficient Heuristic Procedure for Partitioning Graphs. BSTJ. 49, 1970; 291–307.
  • Russo (R L) and Wolff (P K). A Computer-Based Design Approach to Partitioning and Mapping of Computer Logic Graphs. Proc. IEEE. 60, 1; 1972; 28–34.
  • Stone (HS). An Algorithm for Modular Partitioning. J. ACM. 17, 1; 1970; 182–195.
  • Rutman (R A). An Algorithm for Placement of Inter connected Elements Based on Minimum Wire Length. AFIPS Conf. Proc. SJCE, 1964; P 477–491.
  • Hanan (M) and Kurtzberg (J). A Review of the Placement and Quadratic Assignment Problems. SIAM Rev. 2, 1972; 324–342.
  • Schuler (D M) and Ulrich (G). Clustering and Linear Placement. Proc. of 9th Annual Design Automation Workshop. June 1972. P 50–56.
  • Prim (R C). Shortest Connection Networks and Some Generalizations. BSTJ. 1957; 1389–1401.
  • Gilbert (E N) and Pollak (H O). Steiner Minimal Trees. SIAM J. Math. 16, 1968; 1–29.
  • Hanan (M). On Steiner's Problem with Rectilinear Distance. SIAM J. Appl. Math. 14, 1966; 255–265.
  • Lee (J H), Bose (N K) and Hwang (F K). Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric. IEEE Trans. CAS-23, 7; 1976; 470–476.
  • Rubin (F). Assigning Wires to Layers of a Printed Circuit Board. Proc. Des. Auto. Workshop, 1973; P 22–32.
  • Lee (C). An algorithm for Path Connections and its Applications. IRE Trans. Electronic Computer. 1961; 346–365.
  • Geyer (J M). Connection Routing Algorithm for Printed Circuit Design. IEEE Trans. CT-18, 1; 1971; 95–100.
  • Hightower (D). A Solution to Line Routing Problems on the Continuous Plane. Proc. Design Automation Workshop, 1969; P 1–24.
  • Mikami (K) and Tabuchi (K). A Computer Programme for Optimal Routing of Printed Circuit Conductors. Proc. IFIP Congress, 1968; P 1475–1478.
  • Hitchcock (R B). Cellular Wiring and the Cellular Modelling Technique. Proc. Design Auto. Workshop, 1969; P 25–41.
  • Lass (SE). Automated Printed Circuit Routing with a Stepping Aperture. Comm. of ACM. 12, 5; 1969; 262–265.
  • Hashimoto (A) and Stevens (J). Wire Routing by Optimized Channel Assignment with Large Apertures. Proc. Design Auto. Workshop, 1971; P 155–169.
  • Wu (W) and Schmidt (D C). A Floating via Router Based on a Saturated Zone Strategy. IEEE Trans. CAS-23 12 1976; 829–835.
  • So (H C). Some Theoretical Results on the Routing of Multilayer Printed Wiring Boards. Proc. 1974 IEEE International Symp. on Circuits and Systems. P 296–303.
  • Ting (B S), Kuh (E S) and Shirakawa (I). The Multi layer Routing Problem: Algorithms and Necessary Sufficient Conditions for the Single-Row Single-Layer Case. IEEE Trans. CAS-23, 12; 1976; 768–778.
  • Kawanishi (H), Goto (S) and Oyamada (T). A Routing Method of Building Block LSI. Conf. Ree. Seventh Asilomar Conf. Circuits, Systems, Computers, Monterey, California, Nov. 1973. P 119–122.
  • Vancleemput (W M) and Linders (JG). An Improved Graph-Theoretic Model for the Circuit Layout Problem Proc. Design Auto. Workshop, 1974; P 82–90.
  • Vancleemput (W M). Mathematical Models for the Circuit Layout Problem. IEEE Trans. CAS-23, 12; 1976; 759–767
  • Goldstein (A J) and Schweikert (D G). A Proper Model for Testing the Planarity of Electrical Circuits BSTJ 52, 1; 1973; 135–142.
  • Engl (W L), Mlynski (D A) and Pernards (P). Theory of Multiplace Graphs. IEEE Trans. CAS-22, 1. 1975. 717–725.
  • Fisher (G I) and Wing (O). Computer Recognition and Extraction of Planar Graphs from the Incidence Matrices. Ibid. CT-13; 1966; 156–163.
  • Tarjan (R E). Depth First Search and Linear Graph Algorithms. SIAM J. Comp. 1972; 146–160.
  • Hobbs (A M). Survey of Thickness. Recent Progress in Combinatorics, ed. by W.T. Tutte. 1969. Academic Press. P 245–264.
  • Erdos (P) and Guv (R K). Crossing Number Problems. The American Mathematical Soc. 80, 1; 1973; 52–58.
  • Bose (N K) and Prabhu (K A). Thickness of Graphs with Degree Constrained Vertices. IEEE Trans. CAS-24, 4; 1977; 184–190.
  • Prabhu (K A). Automate Wire Routing in Rectilinear Metric. M.S.E.E. Thesis, University of Pittsburgh, PA, USA, April 1977.
  • Hosking (K H). Automatic Printed Circuit Board Routing with Intermediate Control of the Tracking. Computer-Aided Design, IPC Sciences and Tech. Press Ltd., England. 1976; P 149–156.
  • Hoglund (I) and Berg (H). L.S.I. Circuit Design. Ibid 1976. P 165–174.
  • Miron (G J) and Tarrant (S R). The Automatic Printed Wire Routing System of BACKIS. Proc. Design Automation Conf., 1975. P 311–316.
  • Persky (G) and Gummel (H K). Grafos—a Symbolic Routing Language, Proc. Design Automation Workshop, 1973; P 173–181.
  • Bose (N K) and Lee (J H). Steiner's Problem and its Use in Suboptimal Routing. Proc. Ninth Annual Asilomar Conf. on Circuits, Systems, Computers. Nov. 1975, P 48–53.
  • Hwang (FK). On Steinep Minimal Trees with Recilinear Distance. SIAM Applied Math. 1; 1976; 104–114.
  • Karp (R M). Reducibility among Combinatorial Problems. Univ. of California, Berkeley, Computer Science Technical Rept. No. 3, April 1972.
  • Johnson (D). Approximate Algorithms for Combinatorial Problems. J. Comput Syst. Scis. 8, 3 Dec. 1974; 256–278.
  • Horowitz (E) and Sahni (S). Exact and Approximate Algorithms for Scheduling Nonidentical Processors. J. ACM. 23, 2; 1976; 317–327.
  • Sahni (S) and Gonzalez (T). P-Complete Approximation Problems. Ibid. 23, 3; 1976; 555–565.

ADDITIONAL REFERENCES

  • Breuer (M A), Ed. Design Automation of Digital Systems. 1972. Vol. 1, Prentice-Hall, N.J.
  • Breuer (M A), Ed. Digital System Design Automation: Languages, Simulation, and Data Base. Computer Science, Calif. 1975.
  • Francis (R L) and White (J A). Facility Layout and Location: An Analytical Approach. 1974. Prentice-Hall, NJ.
  • Hightower (D W). The Interconnection Problem—a Tutorial. Computer. 7, 4; 1974; 18–32.
  • Knowels (R). Automatic Testing: Systems and Applitions. 1976. Mcgraw-Hill Book Co., NY.
  • Melzak, (Z A). Companion to Concrete Mathematics. 1976. Wiley-Interscience, NY.
  • Povlick (T). Implementation of a Routing Algorithm Using Heapsort. M. S. Thesis. Univ. of Pittsburgh. 1977

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.