Felix Broberg

Förutsägelseassisterad fullkomligt dynamisk effektiv resistens för samtliga noder

Sammanfattning

Vi undersöker den approximativa och fullkomligt dynamiska effektiva resistensen för samtliga noder i en förutsägelseassisterad miljö. Vi skapar en förutsägelsemodell för att förutspå vilka nodpar som är del av framtida kanttillägg, kantborttagningar och förfrågningar om den effektiva resistensen. Modellen är generell nog at vara kompatibel med forskning inom länkförutsägelse inom grafer och kan användas av andra forskare inom förutsägelseassisterade algoritmer. Ett smärre bidrag är att vi skapar den hittills bästa algoritmen för offline-varianten av problemet. Vårt största bidrag är i formen av en datastruktur för att bibehålla den effektiva resistensen mellan samtliga noder som använder sig av den skapade förutsägelsemodellen. Körtiden matchar den bästa algoritmen för offline-varianten av problemet om förutsägelserna är bra, medan den matchar den bästa datastrukturen för online-varianten om förutsägelserna är dåliga.