Leírás
Néhány jól ismert P-beli, gráfokon vagy mátrixokon adott számítási feladatra
adunk az eddig ismerteknél gyorsabb algoritmust kis fa-vastagság esetén. Egy n
x n-es M mátrix fa-vastagsága alatt annak az n csúcsú gráfnak a fa-vastagságát
értjük, melyben i és j akkor van összekötve, ha M[i,j] vagy M[j,i] nem
nulla. Adott n csúcsú G gráf, D digráf vagy egy n x n-es M mátrix, és egy
hozzá tartozó k vastagságú fa-felbontás. A következőket bizonyítjuk:
-- M rangja és determinánsa O(k^3 n) lépéssel kiszámítható.
-- Mx=b lineáris egyenletrendszer O(k^3 n) lépéssel kiszámolható.
-- Létezik O(k^3 n log n) idejű randomizált algoritmus egy G-beli maximális
párosítás méretének meghatározására.
-- Létezik O(k^4 n log^2 n) idejű randomizált algoritmus egy G-beli
maximális párosítás meghatározására.
-- Létezik O(k^2 n log n) idejű algoritmus mely adott s és t között megad
belsőleg pontdiszjunkt D-beli (s,t)-utak egy maximális méretű családját.
A fentieken túl a fa-vastagság approximálására is adunk egy, a fenti célok
eléréséhez passzoló algoritmust, mely k favastagság esetén egy O(k^2)
méretű felbontást ad O(k^7 n log n) időben.