| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
Aplikacije teorije grafov v komunikacijskih omrežjih
Maja Čevnik, 2015, doctoral dissertation

Abstract: 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 n)$. 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 n)$. Kot stranski produkt bomo podali še shemo razširjanja vseh vozlišč v $k$-omejenem kaktusu in center razširjanja $k$-omejenega kaktus grafa. noindent 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 $alpha<0$ in $alpha>1$, podali bomo tudi nekaj delnih rezultatov za primer, ko je $0Keywords: enovozliščno razširjanje, kaktus graf, čas razširjanja, shema razširjanja, center razširjanja, Wienerjevo število, usmerjen graf, komunikacijska omrežja, usmerjena komunikacijska omrežja
Published: 13.04.2015; Views: 1134; Downloads: 85
.pdf Full text (567,00 KB)

Search done in 0.05 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica