Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Chmiel K.

1 1998

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: DCRP

Sortuj według:

Ogranicz wyniki do:

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

Chmiel K.

Studia z Automatyki i Informatyki

1998

T. 23

53-82

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.

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.