On the contact-minimization-problem

1. F. Barahona: “Sur la complexité du problème du verre de spins” Rapport de Recherche 171, Octobre 1979, Université Scientifique Et Medicale et Institut National Polytechnique de Grenoble, Mathematiques Appliquées et Informatique.

   Google Scholar 

2. M. Brady, D. Brown: “VLSI Routing: Four Layers Suffice” Advances in Computing Research, vol. 2 pages 245–257, JAI Press Inc London.

   Google Scholar 

3. M. Ciesielski, E.Kinnen: “An Optimum Layer Assignment for Routing in IC's and PCB's” Proceedings of the 18th Design Automation Conference, June 1981, pp. 733–737.

   Google Scholar 

4. H. Gabow: “Implementation of Algorithms for Maximum Matching on Non-Bipartite Graphs” Ph.D. Dissertation, Stanford University 1973.

   Google Scholar 

5. M. Garey, D. Johnson: “Computers and Intractability: A Guide to the Theory of NP-completeness” W.H.Freeman & co., San Francisco, 1979

   Google Scholar 

6. Y. Kajitani: “On Via Hole Minimization of Routing on a 2-layer Board” Proceedings of the ICCC 1980, pp.295–298

   Google Scholar 

7. W. Lipski: “An NP-complete problem related to three layer channel routing” Manuscript, Institute of Computer Science, PAS, Warsaw, Poland 1982.

   Google Scholar 

8. S. MacLane: “A combinatorial condition for planar graphs” Fundamenta Math. 28, 22–32 (1937)

   Google Scholar 

9. P. Molitor: “Layer Assignment by Simulated Annealing” North-Holland, Microprocessing and Microprogramming 16 (1985), pp.345–350

   Google Scholar 

10. R.Y.Pinter: “Optimal Layer Assignment for Interconnect” Proceedings of the ICCC 1982, pp.398–401

    Google Scholar 

Download references