Login
Lupa
First page / Show document

Show document Help

A- | A+ | Print
Title:Linear separation of connected dominating sets in graphs
Authors:ID Chiarelli, Nina (Author)
ID Milanič, Martin (Author)
Files:.pdf RAZ_Chiarelli_Nina_i2019.pdf (648,51 KB)
MD5: B74258D128B41046ABB25C3E42FBD136
 
Language:English
Work type:Unknown
Typology:1.01 - Original Scientific Article
Organization:ZUP - University of Primorska Press
Keywords: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
Year of publishing:2019
Number of pages:str. 487-525
Numbering:Vol. 16, no. 2
PID:20.500.12556/RUP-11167 This link opens in a new window
UDC:519.17
ISSN on article:1855-3966
DOI:10.26493/1855-3974.1330.916 This link opens in a new window
COBISS.SI-ID:1541145284 This link opens in a new window
Publication date in RUP:04.04.2019
Views:3418
Downloads:162
Metadata:XML DC-XML DC-RDF
:
CHIARELLI, Nina and MILANIČ, Martin, 2019, Linear separation of connected dominating sets in graphs. Ars mathematica contemporanea [online]. 2019. Vol. 16, no. 2, p. 487–525. [Accessed 3 April 2025]. DOI 10.26493/1855-3974.1330.916. Retrieved from: https://repozitorij.upr.si/IzpisGradiva.php?lang=eng&id=11167
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Ars mathematica contemporanea
Publisher: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 This link opens in a new window

Secondary language

Language:Slovenian
Title:Linearna separacija povezanih dominantnih množic v grafih
Abstract: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.
Keywords: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


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica