izpis_h1_title_alt

Algorithms for finding the strongly connected components of directed graphs
LANG, INA (Avtor), Dobravec, Tomaž (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (2,01 MB)
MD5: F2E983C96BADF072DF04402B1DAA564F

Izvleček
One of the most common problems in graph theory is the problem of finding strongly connected components (SCCs). Decomposing a directed graph into strongly connected components is a fundamental tool in graph theory with applications in compiler analysis, data mining, scientific computing, and other areas. In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex in that graph. The strongly connected components of an arbitrary directed graph form a partition into subgraphs. Those subgraphs are themselves strongly connected. In this bachelor thesis, we will introduce the problem mentioned above in detail. We will try to understand its importance by looking at its applications. Then we will proceed exploring different approaches for finding strongly connected components of a directed graph. Finally, we will inspect their advantages and disadvantages by comparing them and draw a conclusion as to which algorithm performs best in a given situation.

Jezik:Angleški jezik
Ključne besede:graph, strong connectivity, strongly connected, Tarjan’s algorithm, Kosaraju’s algorithm, Gabow, path-based, Blelloch, Fleischer, parallelism.
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2021
COBISS.SI-ID:77685251 Povezava se odpre v novem oknu
Število ogledov:61
Število prenosov:11
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
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...

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Algoritmi za iskanje močno povezanih komponent usmerjenih grafov
Izvleček:
Eden od najpogostejših problemov v teoriji grafov je problem iskanja močno povezanih komponent usmerjenega grafa. Razgradnja samega usmerjenega grafa v močno povezane komponente predstavlja pomembno orodje v teoriji grafov, ki je uporabno pri analizi prevajalnikov, podatkovnem rudarjenju in na ostalih področjih. V matematični teoriji pravimo, da je graf močno povezan, če za vsaki dve njegovi vozlišči velja, da sta dosegljivi med seboj. Prav tako mora za vsako od močno povezanih komponent poljubnega usmerjenega grafa veljati, da tudi sama predstavlja močno povezan graf. V tem diplomskem delu bomo podrobno predstavili zgoraj omenjeni problem. Preko njegove aplikacije bomo poskušali razumeti njegov pomen. Nato bomo raziskali različne pristope za iskanje močno povezanih komponent usmerjenih grafov. Na koncu bomo s primerjavo preučili njihove prednosti in pomanjkljivosti ter iz tega sklepali, kateri algoritem je ustrezen v določeni situaciji.

Ključne besede:graf, močna povezanost, močno povezane komponente, Kosaraju, Tarjan, Gabow, Blelloch, Fleischer, vzporednost.

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

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

Nazaj