Kinetisk minimumspännande träd

Ett kinetiskt minimumspännande träd är en kinetisk datastruktur som upprätthåller minsta spännträd (MST) för en graf vars kantvikter ändras som en kontinuerlig funktion av tiden.

Allmänt fall

Den mest effektiva kända datastrukturen för det allmänna fallet använder en kinetisk sorterad lista för att lagra kantvikterna och en standard MST-algoritm för att beräkna MST givet de sorterade kantvikterna. Denna datastruktur måste bearbeta ${\displaystyle O(n^{2})}-$ händelser, att utveckla en mer effektiv datastruktur förblir ett öppet problem.

H-moll-fria grafer

Agarwal et al. utvecklat en datastruktur som upprätthåller MST för en graf som tillhör en mindre sluten familj . Den använder idén om ett "swap", beräknar hur mycket vikten av MST skulle öka om någon kant i trädet e ersattes med en kant f utanför trädet så att cirkeln inducerad av f i trädet innehåller e . Att underhålla trädet motsvarar då att hitta och byta nästa par för vilket denna kvantitet blir negativ. Denna datastruktur tar hänsyn till den dubbla vyn av grafen och delar sedan upp baserat på Fredericksons begränsade partitioner för att göra detta effektivt. Det resulterar i en total körtid $O(pn^{\frac {1}{2}}\log ^{\frac {3}{2}}n )$ om $p$ infogar eller raderingar görs, eller $O(n^{\frac {19}{12}}\log ^{\frac {3}{2}}n)$ om endast viktändringar är tillåtna. Dessa deterministiska gränser förbättras något om randomisering tillåts.

Vidare läsning

Agarwal, Pankaj; Eppstein, David; Guibas, Leonidas J.; Henzinger, Monika R. (1998). Parametriska och kinetiska minsta spännträd (PDF) . FOCS . Hämtad 19 maj 2012 .