Rendszeroptimalizálás, 24. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés (biz. nélkül).

Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben

Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. Minden ilyen feladat megoldható kétrétegű áramköri lapon, megszorítás nélküli modellben alkalmas (nem feltétlenül optimális) szélességben, ilyen megoldást lineáris időben találhatunk.

Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket:

• ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást
• egyenes bekötések (| alak): sorrent érdektelen, nem metszhetik egymást
• ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben

Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a 23. tételben említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus.

Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés

Switchbox-huzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap mind a négy oldalán elhelyezkedhetnek. Erre az esetre Hambrusch tétele kimondja, hogy tetszőleges k számhoz található olyan feladat, amely nem oldható meg k rétegen még a megszorítás nélküli modellben sem.

TODO: bizonyítás

Alső és felső becslés a rétegek számára

[math]\lceil m \rceil + 1 \leq k \leq 2\lceil m \rceil + 4[/math] ahol m = max(n / w, w / n), n és w pedig a lap magassága ill. szélessége

-- dnet - 2010.05.24.