On the computational complexity of upper fractional domination

GA Cheston, G Fricke, ST Hedetniemi… - Discrete Applied …, 1990 - Elsevier
GA Cheston, G Fricke, ST Hedetniemi, DP Jacobs
Discrete Applied Mathematics, 1990Elsevier
This paper studies a nondiscrete generalization of Γ (G), the maximum cardinality of a
minimal dominating set in a graph G=(V, E). In particular, a real-valued function⨍: V→[0, 1],
is dominating if for each vertex υ ϵ V, the sum of the values assigned to the vertices in the
closed neighborhood of υ, N [υ], is at least one, ie,⨍(N [υ])≥ 1. The weight of a dominating
function⨍ is⨍(V), the sum of all values⨍(υ) for υ ϵ V, and Γ⨍(G), is the maximum weight over
all minimal dominating functions. In this paper we show that:(1) Γ⨍(G) is computable and is …
This paper studies a nondiscrete generalization of Γ (G), the maximum cardinality of a minimal dominating set in a graph G=(V, E). In particular, a real-valued function⨍: V→[0, 1], is dominating if for each vertex υ ϵ V, the sum of the values assigned to the vertices in the closed neighborhood of υ, N [υ], is at least one, ie,⨍(N [υ])≥ 1. The weight of a dominating function⨍ is⨍(V), the sum of all values⨍(υ) for υ ϵ V, and Γ⨍(G), is the maximum weight over all minimal dominating functions. In this paper we show that:(1) Γ⨍(G) is computable and is always a rational number;(2) the decision problems corresponding to the problems of computing Γ (G) and Γ⨍(G) are NP-complete;(3) for trees Γ⨍= Γ, which implies that the value of Γ⨍ can be computed in linear time.
Elsevier
Showing the best result for this search. See all results