Dominating set games. (Q703283): Difference between revisions
From MaRDI portal
Latest revision as of 17:06, 7 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dominating set games. |
scientific article |
Statements
Dominating set games. (English)
0 references
11 January 2005
0 references
This paper presents several representation theorems for the solubility of three cost allocation problems, which are presented as cooperative games. In each problem, a graph \(G = (V, E)\) is given along with a cost function: given \(S \subseteq V\), \(c(S)\) is the cost of \(k\)-dominating the vertices in \(S\), i.e., building a set \(K \subseteq V\) such that every vertex in \(S\) is within distance \(k\) (under an appropriate distance metric) of an element of \(K\). The three problems are associated with three cost functions: given a vector \(w \in \mathbb R^{| V| }\) and a positive integer \(k\): 1) The \textit{rigid dominating set game} requires that \(K \subseteq S\) and that distance is measured along edges within the restriction of \(G\) to \(S\). 2) The \textit{intermediate dominating set game} still requires that \(K \subseteq S\), but allows distance to be measured along any paths in \(G\). 3.) The \textit{relaxed dominating set game} drops the requirement that \(K \subseteq S\). The primary result is a representation theorem that asserts that all three games are soluble (i.e., have non-empty cores) simultaneously.
0 references
cooperative cost game
0 references
cost allocation
0 references
dominating set
0 references
dominating set game
0 references
TU game
0 references
0 references