-
Computational complexity aspects of super dominationBujtás, Csilla ; Ghanbari, Nima ; Klavžar, SandiNaj bo ▫$G$▫ graf. Dominantna množica ▫$D\subseteq V(G)$▫ je super dominantna množica, če za vsako vozlišče ▫$x\in V(G) \setminus D$▫ obstaja ▫$y\in D$▫ tako, da je ▫$N_G(y)\cap (V(G)\setminus D)) = ... \{x\}$▫. Kardinalnost najmanjše super dominantne množice ▫$G$▫ je število super dominacije ▫$G$▫. Pridobljena je natančna formula za super dominacijsko število drevesa ▫$T$▫ in dokazano je, da je najmanjšo super dominantno množico ▫$T$▫ mogoče izračunati v linearnem času. Dokazano je, da je NP-polno odločiti, ali je število super dominacije grafa ▫$G$▫ kvečjemu določeno celo število, če je ▫$G$▫ dvodelen graf z ožino vsaj ▫$8$▫. Število super dominacije je določeno za vse ▫$k$▫-subdivizije grafov. Zanimivo je, da lahko v polovici primerov natančno vrednost učinkovito izračunamo iz dobljenih formul, v drugih primerih pa je izračun težaven. Pri pridobivanju teh formul so uvedena števila II-prirejanja in dokazano je, da jih je računsko težko določiti.Source: Theoretical computer science. - ISSN 0304-3975 (Vol. 975, art. no. 114137, Oct. 2023, 14 str.)Type of material - article, component part ; adult, seriousPublish date - 2023Language - englishCOBISS.SI-ID - 162318851
Author
Bujtás, Csilla |
Ghanbari, Nima |
Klavžar, Sandi
Topics
število super dominacije |
drevesa |
dvodelni grafi |
k-subdivizija grafa |
računska zahtevnost |
prirejanje |
število II-prirejanja |
super domination number |
trees |
bipartite graphs |
k-subdivision of a graph |
computational complexity |
matching |
II-matching number
Author | Bujtás, Csilla ; Ghanbari, Nima ; Klavžar, Sandi |
Title | Computational complexity aspects of super domination |
Publication date | 2023-08-18 |
COBISS.SI-ID | 162318851 |
Publication version in repository | Publisher's version |
Publication licence | Creative Commons Attribution 4.0 International |
Embargo | Immediate publication for public |
Project(s) from which the publication was funded
Title | Acronym | Project ID | Funder |
---|---|---|---|
Teorija grafov | P1-0297-2022 |
Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije |
|
Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov | J1-2452-2020 |
Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije |
|
Metrični problemi v grafih in hipergrafih | N1-0285-2023 |
Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije |
Files that belong to the publication
Link |
---|
https://www.sciencedirect.com/science/article/pii/S0304397523004504 |
https://dirros.openscience.si/IzpisGradiva.php?id=18405 |
https://repozitorij.uni-lj.si/IzpisGradiva.php?id=153123 |
source: Theoretical computer science. - ISSN 0304-3975 (Vol. 975, art. no. 114137, Oct. 2023, 14 str.)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Bujtás, Csilla | 52672 |
Ghanbari, Nima | |
Klavžar, Sandi | 05949 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.