izpis_h1_title_alt

Algorithms for finding the strongly connected components of directed graphs
LANG, INA (Author), Dobravec, Tomaž (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (2,01 MB)
MD5: F2E983C96BADF072DF04402B1DAA564F

Abstract
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.

Language:English
Keywords:graph, strong connectivity, strongly connected, Tarjan’s algorithm, Kosaraju’s algorithm, Gabow, path-based, Blelloch, Fleischer, parallelism.
Work type:Bachelor thesis/paper (mb11)
Tipology:2.11 - Undergraduate Thesis
Organization:FRI - Faculty of computer and information science
Year:2021
COBISS.SI-ID:77685251 This link opens in a new window
Views:107
Downloads:20
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:Slovenian
Title:Algoritmi za iskanje močno povezanih komponent usmerjenih grafov
Abstract:
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.

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

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back