izpis_h1_title_alt

Karakterizacije kografov in algoritma za izračun varnostne dominacije na kografih : magistrsko delo
ID Kišek, Anja (Avtor), ID Klavžar, Sandi (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (857,80 KB)
MD5: 9C0A26277E0A10E284D8F7A7E8622013

Izvleček
V delu obravnavamo kografe, njihovo reprezentacijo s kodrevesi in karakterizacijo kografov. Uvrstimo jih v družino popolnih grafov in raziščemo problem barvanja kografov. Poleg algoritma za barvanje navedemo nekaj algoritmov, ki zaradi strukture kodrevesa delujejo v linearnem času, med njimi dominacijo in varnostno dominacijo. Slednjo definiramo in raziščemo njene lastnosti. Obravnavamo dva neodvisna algoritma za iskanje varnostnodominantnega števila na kografih in argumentiramo njuno linearnost.

Jezik:Slovenski jezik
Ključne besede:kograf, kodrevo, varnostnodominantno število, dominantno število, popoln graf, linearen algoritem
Vrsta gradiva:Magistrsko delo/naloga
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2021
PID:20.500.12556/RUL-126403 Povezava se odpre v novem oknu
UDK:519.1
COBISS.SI-ID:60413955 Povezava se odpre v novem oknu
Datum objave v RUL:21.04.2021
Število ogledov:784
Število prenosov:130
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Characterisation of cographs and two algorithms for computation of secure domination number of a cograph
Izvleček:
This work studies cographs, their representation with cotrees and their different characterisations. By observing their colorings, cographs are proved to be a special case of perfect graphs. In addition, a few linear algorithms that exploit the structure of cotrees are presented. Security domination of a graph is introduced and some properties, crucial for its computation are presented. Two independent algorithms for security domination number of cographs are studied and their linearity is argumented.

Ključne besede:cograph, cotree, security domination number, domination number, perfect graph, linear algorithm

Podobna dela

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

Nazaj