Prowadzenie połączeń przez kanał dla problemów MID-DCRP

• Autorzy: Chmiel K.

Warianty tytułu

EN

Channel routing for MID-DCRP problems

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważana jest podklasa problemów o maksymalnej gęstości międzykolumnowej (MID-DCRP) klasy problemów gęstych DCRP. Przebadana została struktura tej klasy z punktu widzenia charakterystyki rozwiązania (Is, II, Ip), gdzie Is oznacza liczbę ścieżek, a II i Ip liczbę odpowiednio, lewych i prawych kolumn dodatkowych. Na tej podstawie wskazany został wielomianowy algorytm, prowadzący do optymalnego rozwiązania przy dwustopniowym kryterium liczby ścieżek i liczby kolumn.

EN

In the paper the class of maximum intercolumn density dense channel routing problems (MID-DCRP) is considered. The structure of the class with respect to the solution characteristic (Is, II, Ip) is investigated, where Is denotes the number of tracks and II, Ip denote the number of left and right additional columns, respectively. Presented results indicate a polynomial time algorithm, leading to the optimal solution in terms of the two level criterion: number of tracks - number of columns.

Słowa kluczowe

PL

DCRP; algorytm zachłanny

EN

DCRP; greedy algorithm

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 1998
• Tom: T. 23
• Strony: 53--82
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Chmiel K.

• Politechnika Poznańska, Katedra Automatyki, Robotyki i Informatyki, Pl. M. Skłodowskiej-Curie 5, 60-965 Poznań

Bibliografia

• [1] Brown D.J., Rivest R.L.: New Lower Bounds for Channel Width. Proc. 1981 CMU Conf. VLSI Systems and Computations, 1981, s. 178-185.
• [2] Burstein M., Pelavin R.: Hierarchical Channel Router. INTEGRATION, the VLSI Journal, 1, 1983, s. 21-38.
• [3] Deutsch D.N.: A Dogleg Channel Router. Proc. of the 13th Design Automation Conference, 1976, s. 425-433.
• [4] Forman M., Wagner D., Wagner F.: Routing through a Dense Channel with Minimum Total Wire Length, 1989.
• [5] LaPaugh A.S.: Algorithms for Integrated Circuit Layout: An Analytic Approach. Ph.D. Thesis, Laboratory for Computer Science, MIT, 1980.
• [6] Ohtsuki T.: Layout Design and Verification. North Holland, 1986.
• [7] Rivest R.L., Fiduccia C.M.: A Greedy Channel Router. Proc. of the I9th Design Automation Conference, 1982, s. 418-424.
• [8] Szymanski T.G.: Dogleg Channel Routing is NP-complete. IEEE Trans. on CAD, CAD-4, 1, January 1985, s. 31-40.
• [9] Voshimura T., Kun E.S.: Efficient Algorithms for Channel Routing. IEEE Trans. on CAD, V. CAD-1, 1, 1982, s. 25-35.