20.500.12556/RUP-11167 Linear separation of connected dominating sets in graphs Linearna separacija povezanih dominantnih množic v grafih 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. 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 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 true true false Angleški jezik Slovenski jezik Neznano 2019-04-04 08:14:22 2019-04-04 08:14:23 2024-03-01 13:54:53 0000-00-00 00:00:00 2019 0 0 str. 487-525 no. 2 Vol. 16 2019 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1855-3966 10.26493/1855-3974.1330.916 1541145284 RAZ_Chiarelli_Nina_i2019.pdf RAZ_Chiarelli_Nina_i2019.pdf 1 B74258D128B41046ABB25C3E42FBD136 b6a7cd5e280a972a0cd2e17e5a3166fddb2b3506d859931e3cd2a2cf739e7baa 78b56411-c3d6-11ed-b5df-005056bf369b https://repozitorij.upr.si/Dokument.php?lang=slv&id=25954 Založba Univerze na Primorskem 0 0 0