Dominating set games.

DOI10.1016/J.ORL.2004.02.004MaRDI QIDQ703283zbMATH OpenOpenAlexFDO

Authors Bas van Velzen

Publication date 11 January 2005

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2004.02.004

zbMATH Keywords

cooperative cost gamecost allocationdominating setdominating set gameTU game

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Discrete location and assignment (90B80) Cooperative games (91A12) Games involving graphs (91A43) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Review text

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.

Recommendations

• A note on balancedness of dominating set games
• BALANCEDNESS OF INTEGER DOMINATION GAMES
• The cores of paired-domination games
• CORE STABILITY OF DOMINATING SET GAMES
• Balancedness of edge covering games

Cites work

• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Balanced matrices
• Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem
• Graphs whose neighborhoods have no special cycles
• scientific article; zbMATH DE number 9246 (Why is no real title available?)
• scientific article; zbMATH DE number 16723 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Ideal 0, 1 matrices
• On the Core of Cost Allocation Games Defined on Location Problems
• Relations between packing and covering numbers of a tree

Cited in

(7)

• A game theoretic approach for minimal connected dominating set
• Balancedness of edge covering games
• A note on balancedness of dominating set games
• On the cores of games arising from integer edge covering functions of graphs
• BALANCEDNESS OF INTEGER DOMINATION GAMES
• The cores of paired-domination games
• Approximate core allocations for edge cover games

This page was built for publication: Dominating set games.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703283)