| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Aplikacije teorije grafov v komunikacijskih omrežjih
Avtorji:Čevnik, Maja (Avtor)
Žerovnik, Janez (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf EDOK_Cevnik_Maja_2015.pdf (567,00 KB)
MD5: D6605B3A302CB22FBFBEBB5529CF1FC5
 
Jezik:Slovenski jezik
Vrsta gradiva:Doktorska disertacija (m)
Tipologija:2.08 - Doktorska disertacija
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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 $0<alpha <0.$
Ključne besede: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
Leto izida:2015
Založnik:M. Čevnik]
Izvor:[Maribor
UDK:519.17:004.7(043.3)
COBISS_ID:21305608 Novo okno
NUK URN:URN:SI:UM:DK:2LSLKXV7
Število ogledov:1134
Število prenosov:85
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Applications of graph theory in communication networks
Opis:Good communication between the units in a communication network or among the proccessors in a parallel system is essential for the proper functioning. There are various problems of communication that can be transformed to the problems of graph theory. Since several of these problems are NP-hard, we focus on solving subproblems which can be solved in polynomial time. One of popular problems of information dissemination is broadcasting. Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between neighboring vertices while we follow some rules. In disertation broadcasting in cactus graphs is studied. An algorithm that determines broadcast time of any originator with time complexity $O(n log Delta)$ in $ k$-restricted cactus graph is given. Furthermore, another algorithm which calculates broadcast time of all vertices in a $k$-restricted cactus graph and optimal broadcast scheme for each vertex of a graph within the same time complexity is outlined. As a byproduct, broadcast center of a $k$-restricted cactus graph is computed. noindent In the second part of disertation we will talk about another problem associated with communication networks. We will introduce modified Wiener number on directed graphs and we will study digraphs with minimal value for one possible modification of the Wiener number for directed graphs. For digraphs with unique shortest paths we provide minimal digraphs for $alpha<0$ and $alpha>1$, and give some partial results for $0
Ključne besede:broadcasting, cactus graph, broadcast time, broadcast scheme, broadcast center, Wiener number, directed graph, communication network, oriented network


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici