{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-KR4IBKOU/6050675a-f4fd-4b13-9d97-93d26c8fe1a7/PDF","dcterms:extent":"675 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-KR4IBKOU/354aa3dc-2cae-4979-a4de-c23b06c4a8b4/TEXT","dcterms:extent":"116 KB"}],"edm:TimeSpan":{"@rdf:about":"2008-2025","edm:begin":{"@xml:lang":"en","#text":"2008"},"edm:end":{"@xml:lang":"en","#text":"2025"}},"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:doc-KR4IBKOU","dcterms:isPartOf":[{"@rdf:resource":"https://www.dlib.si/details/URN:NBN:SI:spr-UP1WMFAR"},{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"}],"dcterms:issued":"2019","dc:creator":["Chiarelli, Nina","Milanič, Martin"],"dc:format":[{"@xml:lang":"sl","#text":"letnik:16"},{"@xml:lang":"sl","#text":"številka:2"},{"@xml:lang":"sl","#text":"str. 487-525"}],"dc:identifier":["COBISSID_HOST:1541145284","ISSN:1855-3966","URN:URN:NBN:SI:doc-KR4IBKOU"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:subject":[{"@xml:lang":"en","#text":"1-Sperner hypergraph"},{"@xml:lang":"sl","#text":"1-Spernerjev hipergraf"},{"@xml:lang":"sl","#text":"algoritem polinomske časovne zahtevnosti"},{"@xml:lang":"en","#text":"chordal graph"},{"@xml:lang":"en","#text":"connected dominating set"},{"@xml:lang":"en","#text":"connected domination"},{"@xml:lang":"en","#text":"connected-domishold graph"},{"@xml:lang":"en","#text":"forbidden induced subgraph characterization"},{"@xml:lang":"sl","#text":"karakterizacija s prepovedanimi induciranimi podgrafi"},{"@xml:lang":"en","#text":"minimal cutset"},{"@xml:lang":"en","#text":"minimal separator"},{"@xml:lang":"sl","#text":"minimalen prerez"},{"@xml:lang":"sl","#text":"minimalen separator"},{"@xml:lang":"en","#text":"polynomial-time algorithm"},{"@xml:lang":"sl","#text":"povezana dominacija"},{"@xml:lang":"sl","#text":"povezana dominantna množica"},{"@xml:lang":"sl","#text":"povezano dominantno pragoven graf"},{"@xml:lang":"sl","#text":"pragoven hipergraf"},{"@xml:lang":"sl","#text":"pragovna Boolova funkcija"},{"@xml:lang":"sl","#text":"razcepljen graf"},{"@xml:lang":"en","#text":"split graph"},{"@xml:lang":"sl","#text":"tetiven graf"},{"@xml:lang":"en","#text":"threshold Boolean function"},{"@xml:lang":"en","#text":"threshold hypergraph"}],"dcterms:temporal":{"@rdf:resource":"2008-2025"},"dc:title":{"@xml:lang":"sl","#text":"Linear separation of connected dominating sets in graphs|"},"dc:description":[{"@xml:lang":"sl","#text":"A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. Following analogous studies in the literature related to independent sets, dominating sets, and total dominating sets, we study in this paper the class of graphs in which the connected dominating sets can be separated from the other vertex subsets by a linear weight function. More precisely, we say that a graph is connected-domishold if it admits non-negative real weights associated to its vertices such that a set of vertices is a connected dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We characterize the graphs in this non-hereditary class in terms of a property of the set of minimal cutsets of the graph. We give several characterizations for the hereditary case, that is, when each connected induced subgraph is required to be connected-domishold. The characterization by forbidden induced subgraphs implies that the class properly generalizes two well known classes of chordal graphs, the block graphs and the trivially perfect graphs. Finally, we study certain algorithmic aspects of connected-domishold graphs. Building on connections with minimal cutsets and properties of the derived hypergraphs and Boolean functions, we show that our approach leads to new polynomially solvable cases of the weighted connected dominating set problem"},{"@xml:lang":"sl","#text":"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"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:doc-KR4IBKOU","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-KR4IBKOU"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-KR4IBKOU/6050675a-f4fd-4b13-9d97-93d26c8fe1a7/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:doc-KR4IBKOU/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-KR4IBKOU"}}}}