| Title: | Izbrane verzije dominacijskih množic in njihova časovna zahtevnost |
|---|
| Authors: | ID Višnar, Lučka (Author)
ID Peterin, Iztok (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Visnar_Lucka_2021.pdf (694,82 KB)
MD5: 671AE52B2375872EFA6BE61A9AB00470
PID: 20.500.12556/dkum/3256a36f-d0de-40d0-b697-1a5227691338
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | V tem magistrskem delu predstavimo različne dominacijske množice, in sicer popolno, učinkovito ter neodvisno.
V prvem delu so navedeni osnovni pojmi v teoriji grafov, vse potrebne definicije, izreki in trditve. V nadaljevanju predstavimo nekaj znanih NP-polnih problemov s področja dominacije na grafih in jih podkrepimo s primeri za namen dokazovanja časovne zahtevnosti. Za izbrane dominacijske probleme prikažemo kompleksnost odločitvenih problemov z dominacijskimi lastnostmi za glavne dominacijske množice (popolna, učinkovita in neodvisna) in druge izbrane dominacije. Nazadnje posežemo še po problemih popolnega dominacijskega števila za neodvisno, povezano in celotno dominacijo. |
|---|
| Keywords: | dominacijska množica, popolna dominacijska množica, neodvisna dominacijska množica, učinkovita dominacijska množica, NP-polni problemi, dominacijsko število |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [L. Višnar] |
|---|
| Year of publishing: | 2021 |
|---|
| PID: | 20.500.12556/DKUM-79865 |
|---|
| UDC: | 519.17:517.518.2(043.2) |
|---|
| COBISS.SI-ID: | 78385923 |
|---|
| Publication date in DKUM: | 07.10.2021 |
|---|
| Views: | 920 |
|---|
| Downloads: | 49 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
