Na Oddelku za matematiko in računalništvo je doktorirala Maja Čevnik.
Naslov doktorske disertacije je Aplikacije teorije grafov v komunikacijskih omrežjih. Opravljena je bila pod mentorstvom red. prof. ddr. Janeza Žerovnika, komisijo ob zagovoru pa sta poleg mentorja sestavljala še red. prof. dr. Aleksander Vesel in izr. prof. dr. Sergio Cabello Justo.
Dobra komunikacija med enotami omrežja ali med procesorji je bistvenega pomena za dobro delovanje. Veliko problemov, povezanih s komunikacijskimi omrežji ali paralelno arhitekturo, lahko prenesemo v probleme teorije grafov. Ker je dosti izmed teh problemov NP-težkih, se v tem primeru osredotočamo na reševanje podproblemov, ki jih znamo rešiti v polinomskem času. Eden izmed osnovnih problemov usmerjanja informacij v komunikacijskih omrežjih je problem enovozliščnega razširjanja. To je proces razširjanja informacije iz enega (izvornega) vozlišča do vseh ostalih vozlišč grafa z zaporedjem klicev med sosednjimi vozlišči, pri čemer je potrebno upoštevati pravila enovozliščnega razširjanja. V disertaciji se bomo omejili na problem enovozliščnega razširjanja v k-omejenih kaktus grafih, kjer bomo podali algoritem, ki reši problem razširjanja iz izvornega vozlišča v času O(n log Δ). Podali bomo tudi algoritem, ki s pomočjo rezultatov dobljenih ob računanju časa razširjanja izvornega vozlišča, izračuna čas razširjanja vseh vozlišč grafa s časovno zahtevnostjo O(n log Δ). Nazadnje bomo pokazali, da lahko s pomočjo drugačnega načina urejanja zmanjšamo časovno zahtevnost algoritma, ki postane linearen. Kot stranski produkt bomo podali še shemo razširjanja vseh vozlišč v k-omejenem kaktusu in center razširjanja k-omejenega kaktus grafa.
V drugem delu bomo proučevali Wienerjevo število za usmerjene grafe in omenili povezavo z načrtovanjem optičnih omrežij. Izkaže se, da so usmerjeni grafi z ekstremnim modificiranim Wienerjevim številom optimalna omrežja. Proučevali bomo usmerjene grafe z najmanjšo vrednostjo za eno izmed možnih posplošitev Wienerjevega števila za usmerjene grafe. Za digrafe z lastnostjo enolične najkrajše poti bomo podali minimalne digrafe za α<0 in α>1, podali bomo tudi nekaj delnih rezultatov za primer, ko je 0< α <0.
To je petinštirideseti doktorat na Oddelku za matematiko in računalništvo.
