On the computational complexity of upper fractional domination
type: Item
instance of: scholarly article
title: On the computational complexity of upper fractional domination
zbMATH Open document ID: 0717.05068
DOI: 10.1016/0166-218X(90)90065-K
author: Grant A. Cheston
author: Stephen T. Hedetniemi
author: D. P. Jacobs
author: Gerd H. Fricke
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: Two well-studied parameters of graphs are \(\gamma\) (G) and \(\Gamma\) (G), the minimum and maximum cardinality over all minimal dominating sets in G. The authors study a nondiscrete generalization of \(\Gamma\) (G): the maximum weight over all minimal dominating functions \(\Gamma_ f(G)\). They show that (1) \(\Gamma_ f(G)\) is computable and is always a rational number; (2) the decision problems corresponding to the problems of computing \(\Gamma\) (G) and \(\Gamma_ f(G)\) are NP-complete; (3) for trees \(\Gamma_ f(G)=\Gamma (G)\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4181398
zbMATH Keywords: NP-completeness
zbMATH Keywords: maximum weight
zbMATH Keywords: minimal dominating functions
reviewed by: Elkedagmar Heinrich
MaRDI profile type: Publication
cites work: Fractional matchings and covers in infinite hypergraphs
cites work: Packing Problems and Hypergraph Theory: A Survey
cites work: Q3820628
cites work: On the Fractional Covering Number of Hypergraphs
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Q5753985
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Q4194994
cites work: Q3032297
cites work: Solving covering problems and the uncapacitated plant location problem on trees
cites work: Q4123349
cites work: Linear algorithms on recursive representations of trees
cites work: Fractional matchings and the Edmonds-Gallai theorem
cites work: Q3822197
description: scientific article; zbMATH DE number 4181398