최소 경유 2층 인쇄회로기판 배선도의 3-색 알고리즘 = Three Color Algorithm for Two-Layer Printed Circuit Boards Layout with Minimum Via

다국어 초록 (Multilingual Abstract)

The printed circuit board (PCB) can be used only 2 layers of front and back. Therefore, the wiring line segments are located in 2 layers without crossing each other. In this case, the line segment can be appear in both layers and this line segment is to resolve the crossing problem go through the via. The via minimization problem (VMP) has minimum number of via in layout design problem. The VMP is classified by NP-complete because of the polynomial time algorithm to solve the optimal solution has been unknown yet. This paper suggests polynomial time algorithm that can be solve the optimal solution of VMP. This algorithm transforms n-line segments into vertices, and p-crossing into edges of a graph. Then this graph is partitioned into 3-coloring sets of each vertex in each set independent each other. For 3-coloring sets C〈SUB〉i〈/SUB〉,(i=1,2,3) , the C〈SUB〉1〈/SUB〉 is assigned to front F,C〈SUB〉2〈/SUB〉 is back , and C〈SUB〉3〈/SUB〉 is B-F and connected with via. For the various experimental data, though this algorithm can be require O(np) polynomial time, we obtain the optimal solution for all of data.

목차 (Table of Contents)

• Abstract
• Ⅰ. Introduction
• Ⅱ. Crossing and Via Number
• Ⅲ. Three Coloring Algorithm
• Ⅳ. Applications and Evaluation
• Ⅴ. Conclusions
• REFERENCES

참고문헌 (Reference)

1 L. Franuke, "Via Minimization in VLSI Chip Design - Application of a Planar Max-Cut Algorithm" Cologne University 1-15, 2011

2 N. J. Naclerio, "Via Minimization for Gridless Layouts" 159-165, 1987

3 N. A. Sherwani, "Via Minimization and Over-the-Cell Routing" Kluwer Academic Publishers Norwell 1999

4 M. Newton, "Two New Heuristics for Two-Sides Bipartite Graph Drawing" Springer Berlin/Heidelberg 2528 : 465-485, 2002

5 N.J. Naclerio, "The via minimization problem is NP-complete" Institute of Electrical and Electronics Engineers (IEEE) 38 (38): 1604-1608, 1989

6 P. Fouilhoux, "Solving VLSI Design and DNA Sequencing Problems Using Bipartization of Graphs" 51 (51): 749-781, 2012

7 X. Mu~n oz, "One Sided Crossing Minimization is NP-hard for Sparse Graphs" 115-123, 2001

8 Chi-Ping Hsu, "Minimum-Via Topological Routing" Institute of Electrical and Electronics Engineers (IEEE) 2 (2): 235-246, 1983

9 R. Hojati, "Layout Optimization by Pattern Modification" 632-637, 1990

10 M.J. Ciesielski, "Layer assignment for VLSI interconnect delay minimization" Institute of Electrical and Electronics Engineers (IEEE) 8 (8): 702-707, 1989

11 Y. S. Kuo, "Fast Algorithm for Optimal Layer Assignment" 7 (7): 231-245, 1989

12 M. R. Garey, "Crossing Number is NP-complete" 4 (4): 312-316, 1983

13 S. C. Fang, "Constrained Via Minimization with Practical Considerations for Multi-Layer VLSI/PCB Routing Problems" 60-65, 1991

14 R. B. Lin, "Conjugate Conflict Continuation Graphs for Multi-Layer Constrained Via Minimization" 177 (177): 2436-2447, 2007

15 Chin-Chih Chang, "An efficient approach to multilayer layer assignment with an application to via minimization" Institute of Electrical and Electronics Engineers (IEEE) 18 (18): 608-620, 1999

16 M. Marek-Sadowska, "An Unconstrained Topological Via Minimization Problem for Two-Layer Routing" Institute of Electrical and Electronics Engineers (IEEE) 3 (3): 184-190, 1984

17 S. Thakur, "An Optimal Layer Assignment Algorithm for Minimizing Crosstalk for Three Layer VHV Channel Routing" 1 : 207-210, 1995

18 P. Fouilhoux, "An Exact Model for Multi-Layer Constrained Via Minimization" xx (xx): 2004

19 K.-S. The, "A layout modification approach to via minimization" Institute of Electrical and Electronics Engineers (IEEE) 10 (10): 536-541, 1991

20 Ruen-Wu Chen, "A graph-theoretic via minimization algorithm for two-layer printed circuit boards" Institute of Electrical and Electronics Engineers (IEEE) 30 (30): 284-299, 1983

21 R. Noteboom, "A New Graph Coloring Algorithm for Constrained Via Minimization" 1 : 363-366, 1994

22 K. Takahashi, "A Heuristic Algorithm to Solve Constrained Via Minimization for Three-Layer Routing Problems" 6 : 254-257, 1998

23 M. Tang, "A Genetic Algorithm for Constrained Via Minimization" 2 : 435-440, 1999