Prijava
Lupa
Prva stran / Izpis gradiva

Izpis gradiva Pomoč

A- | A+ | Natisni
Naslov:Linear separation of connected dominating sets in graphs
Avtorji:ID Chiarelli, Nina (Avtor)
ID Milanič, Martin (Avtor)
Datoteke:.pdf RAZ_Chiarelli_Nina_i2019.pdf (648,51 KB)
MD5: B74258D128B41046ABB25C3E42FBD136
 
Jezik:Angleški jezik
Vrsta gradiva:Neznano
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:ZUP - Založba Univerze na Primorskem
Ključne besede:connected dominating set, connected domination, connected-domishold graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1-Sperner hypergraph, threshold hypergraph, threshold Boolean function, polynomial-time algorithm
Leto izida:2019
Št. strani:str. 487-525
Številčenje:Vol. 16, no. 2
PID:20.500.12556/RUP-11167 Povezava se odpre v novem oknu
UDK:519.17
ISSN pri članku:1855-3966
DOI:10.26493/1855-3974.1330.916 Povezava se odpre v novem oknu
COBISS.SI-ID:1541145284 Povezava se odpre v novem oknu
Datum objave v RUP:04.04.2019
Število ogledov:3451
Število prenosov:162
Metapodatki:XML DC-XML DC-RDF
:
CHIARELLI, Nina in MILANIČ, Martin, 2019, Linear separation of connected dominating sets in graphs. Ars mathematica contemporanea [na spletu]. 2019. Vol. 16, no. 2, p. 487–525. [Dostopano 5 april 2025]. DOI 10.26493/1855-3974.1330.916. Pridobljeno s: https://repozitorij.upr.si/IzpisGradiva.php?lang=slv&id=11167
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Ars mathematica contemporanea
Založnik:Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
ISSN:1855-3966
COBISS.SI-ID:239049984 Povezava se odpre v novem oknu

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Linearna separacija povezanih dominantnih množic v grafih
Opis:Povezana dominantna množica v grafu je dominantna množica točk, ki inducira povezan podgraf. Po zgledu sorodnih raziskav v literaturi o neodvisnih množicah, dominantnih množicah in totalno dominantnih množicah v tem članku raziskujemo razred grafov, v katerem lahko povezane dominantne množice točk ločimo od ostalih podmnožic točk z linearno utežno funkcijo. Natančneje, pravimo, da je graf povezano dominantno pragoven, če lahko njegovi množici točk priredimo take nenegativne realne uteži, da je množica točk povezana dominantna množica natanko tedaj, ko vsota uteži njenih elementov preseže določen prag. Grafe tega nehereditarnega razreda karakteriziramo s pomočjo množice minimalnih prerezov grafa. Podamo tudi več karakterizacij za hereditarni primer, tj. ko se za vsak povezan induciran podgraf zahteva, da je povezano dominantno pragoven. Karakterizacija s prepovedanimi induciranimi podgrafi implicira, da je ta razred grafov prava posplošitev dobro znanih razredov tetivnih grafov, bločnih grafov in trivialno popolnih grafov. Preučujemo tudi določene algoritmične vidike povezano dominantno pragovnih grafov. Na podlagi povezav z minimalnimi prerezi in lastnostmi izpeljanih hipergrafov in Boolovih funkcij pokažemo, da naš pristop vodi k novim polinomsko rešljivim primerom problema utežene povezane dominantne množice.
Ključne besede:povezana dominantna množica, povezana dominacija, povezano dominantno pragoven graf, karakterizacija s prepovedanimi induciranimi podgrafi, razcepljen graf, tetiven graf, minimalen prerez, minimalen separator, 1-Spernerjev hipergraf, pragoven hipergraf, pragovna Boolova funkcija, algoritem polinomske časovne zahtevnosti


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici