Treffer: Izabrani algoritmi teorije grafova

Title:
Izabrani algoritmi teorije grafova
Authors:
Krstić, Đana
Contributors:
Vukičević, Damir, Šubašić, Aljoša, Vojković, Tanja
Publisher Information:
Sveučilište u Splitu. Prirodoslovno-matematički fakultet., 2024.
Publication Year:
2024
Subject Terms:
adjacency matrix, kanonska strategija sortiranja, TRO algoritam, piece, savršena eliminacijska shema, lexicographic BFS, PRIRODNE ZNANOSTI. Matematika, color class, algorithm complexity, forsiranje, block, TRO algorithm, transitive tournament, matrica susjedstva, G-admissible, množenje vrhova, blok, savršeni graf, NATURAL SCIENCES. Mathematics, G-prihvatljiv, klasa boja, simplex, simpleks, komad, dekompozicijska shema, comparability graph, planarity, points of contact, trianguilirani graf, forcing, labeliranje permutacije, perfect elimination scheme, decomposition scheme, permutation graph, triangulated graph, permutation labeling, tranzitivna orijentacija, leksikografski BFS, graf usporedivosti, mjesta kontakta, transitive orientation, tranzitivni turnir, složenost algoritma, perfect graph, canonical sorting strategy, permutacijski graf, planarnost, multiplication of vertices, lista susjedstva, adjacency list
Document Type:
Dissertation Master thesis
File Description:
application/pdf
Language:
Croatian
Access URL:
https://repozitorij.svkst.unist.hr/islandora/object/pmfst:2013/datastream/PDF
https://urn.nsk.hr/urn:nbn:hr:166:851179
https://repozitorij.svkst.unist.hr/islandora/object/pmfst:2013
Rights:
URL: http://rightsstatements.org/vocab/InC/1.0/
Accession Number:
edsair.dedup.wf.002..b60f0f0dd099a980dbd5df0b4cdfb01f
Database:
OpenAIRE

Weitere Informationen

The thesis is centered on selected algorithms in graph theory. Certain problems, which are usually considered NP-difficult, solvable in polynomial time when applied to specific subclasses of perfect graphs. The thesisThe paper presents algorithms for verifying the correctness of these graph types and their complexity. Additionally, the thesis includes an algorithm for sorting data stored in as a graph, it handles permutation graphs and their coloring, and verification of graph planarity.
Rad je centriran na odabranim algoritmima iz teorije grafova. Pojedini problemi, koji se općenito smatraju NP-teškima, postaju rješivi u polinomijalnom vremenu kad se primijene na specifične podklase savršenih grafova. Rad prikazuje algoritme za provjeru ispravnosti tipa tih grafova i složenost tih algoritama. Osim toga, rad uključuje i algoritam za sortiranje podatka u grafu, bavi se permutacijskim grafovima i njihovim bojanje, te provjeru planarnosti grafa.