VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
-
Spreading in graphsBrešar, Boštjan ...Raziskovanih je bilo več konceptov, ki modelirajo procese razširjanja (informacij, bolezni, predmetov itd.) v grafih ali omrežjih. V mnogih kontekstih predpostavljamo, da so pred začetkom procesa ... nekatera vozlišča grafa ▫$G$▫ kontaminirana. Po pravilu ▫$q$▫-prisile kontaminirano vozlišče, ki ima največ ▫$q$▫ nekontaminiranih sosedov, prisili vse sosede, da postanejo kontaminirani, medtem ko po pravilu ▫$p$▫-pronicanja nekontaminirano vozlišče postane kontaminirano, če je vsaj ▫$p$▫ njegovih sosedov kontaminiranih. Če postanejo glede na podano množico ▫$S$▫ začetno kontaminiranih vozlišč vsa vozlišča na koncu kontaminirana, po kontinuirani uporabi pravila ▫$q$▫-prisile (oziroma pravilo ▫$p$▫-pronicanja), se ▫$S$▫ imenuje množica ▫$q$▫-prisile (oziroma množica ▫$p$▫-pronicanja) v ▫$G$▫. V tem članku obravnavamo množice ▫$S$▫, ki so hkrati množice ▫$q$▫-prisile in ▫$p$▫-pronicanja in jih imenujemo množice ▫$(p,q)$▫-razširjanja. Za dani pozitivni celi števili ▫$p$▫ in ▫$q$▫ je minimalna kardinalnost množice ▫$(p,q)$▫-razširjanja v ▫$G$▫ število ▫$(p,q)$▫-razširjanja grafa ▫$G$▫ in jo označimo s ▫$\sigma_{(p,q)}(G)$▫. Čeprav so bile množice ▫$q$▫-prisile obravnavane v desetinah člankov, odločitvena različica ustrezne grafovske invariante ni bila obravnavana prej, zato zapolnimo to vrzel z dokazom njene NP-polnosti. To nam omogoča dokazati NP-polnost odločitvene različice števila ▫$(p,q)$▫-razširjanja v grafih za poljubna ▫$p$▫ in ▫$q$▫. Ponovno, za vsak ▫$p\in {\mathbb N}$▫ in ▫$q\in {\mathbb N}\cup{\infty}$▫ najdemo algoritem linearne časovne zahtevnosti za določanje števila ▫$(p,q)$▫-razširjanja poljubnega drevesa, kjer v primeru ▫$p\ge 2$▫ uporabimo Riedlov algoritem iz [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] o ▫$p$▫-pronicanju v drevesih. Poleg tega predstavimo spodnjo in zgornjo mejo za število ▫$(p,q)$▫-razširjanja drevesa ter karakteriziramo ekstremne družine dreves. V primeru kvadratnih mrež združimo nekaj rezultatov Bollobáša iz [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006] in delovne skupine AIM Minimum Rank-Special Graphs Work Group iz [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 (2008) 1628-1648] z novimi rezultati o ▫$(2,1)$▫-razširjanju in ▫$(4,q)$▫-razširjanju, da dobimo ▫$\sigma_{(p,q)}(P_m\Box P_n)$▫ za vse ▫$(p,q)\in ({\mathbb N}\setminus{3})\times ({\mathbb N}\cup{\infty})$▫ in vse ▫$m,n \in {\mathbb N}$▫.Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 353, Aug. 2024, str. 139-150)Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasleLeto - 2024Jezik - angleškiCOBISS.SI-ID - 195071235
Avtor
Brešar, Boštjan |
Dravec, Tanja |
Erey, Aysel |
Hedžet, Jaka
Teme
ojačano pronicanje |
ničelna prisila |
drevesa |
kartezična mreža |
bootstrap percolation |
zero forcing |
trees |
grid
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Brešar, Boštjan | 17005 |
Dravec, Tanja | 32028 |
Erey, Aysel | ![]() |
Hedžet, Jaka | 55745 |
Vir: Osebne bibliografije
in: SICRIS
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Naslov za dostavo:
Med podatki člana manjka naslov.
Storitev za pridobivanje naslova trenutno ni dostopna, prosimo, poskusite še enkrat.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in naslov za dostavo ter dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrani naslov za dostavo in dokončali postopek rezervacije.
Obvestilo
Trenutno je storitev za avtomatsko prijavo in rezervacijo nedostopna. Gradivo lahko rezervirate sami na portalu Biblos ali ponovno poskusite tukaj kasneje.
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Gradivo iz matične enote je brezplačno. Če je gradivo na mesto prevzema dostavljeno iz drugih enot, lahko knjižnica to storitev zaračuna.
Mesto prevzema | Status gradiva | Rezervacija |
---|
Rezervacija v teku
Prosimo, počakajte trenutek.
Rezervacija je uspela.
Rezervacija ni uspela.
Rezervacija...
Članska izkaznica:
Mesto prevzema: