On the computational complexity of upper fractional domination
From MaRDI portal
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)\).
Recommendations
Cites work
- Contributions to the theory of domination, independence and irredundance in graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Fractional matchings and covers in infinite hypergraphs
- Fractional matchings and the Edmonds-Gallai theorem
- scientific article; zbMATH DE number 4130427 (Why is no real title available?)
- scientific article; zbMATH DE number 4093496 (Why is no real title available?)
- scientific article; zbMATH DE number 4095510 (Why is no real title available?)
- scientific article; zbMATH DE number 3549014 (Why is no real title available?)
- scientific article; zbMATH DE number 3634298 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4189776 (Why is no real title available?)
- Linear algorithms on recursive representations of trees
- On the Fractional Covering Number of Hypergraphs
- Packing Problems and Hypergraph Theory: A Survey
- Solving covering problems and the uncapacitated plant location problem on trees
Cited in
(32)- The b-chromatic number of a graph
- Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
- The determinant of a tree's neighborhood matrix
- On the computational complexity of upper total domination
- The many facets of upper domination
- Maximal irredundant functions
- Algorithmic aspects of upper edge domination
- (In)approximability of maximum minimal FVS
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Weighted upper domination number
- A constraint generation algorithm for large scale linear programs using multiple-points separation
- Unsolved algorithmic problems on trees
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- A boundary property for upper domination
- Upper domination: complexity and approximation
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Vector representation of graph domination
- The private neighbor concept
- Fractional dominating parameters
- CONVEXITY OF MINIMAL DOMINATING FUNCTIONS OF TREES: A SURVEY
- scientific article; zbMATH DE number 4121429 (Why is no real title available?)
- A maximum dicut in a digraph induced by a minimal dominating set
- scientific article; zbMATH DE number 975353 (Why is no real title available?)
- scientific article; zbMATH DE number 238431 (Why is no real title available?)
- Linear programming approach for various domination parameters
- Complexity of the max cut problem with the minimal domination constraint
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- In)approximability of Maximum Minimal FVS
- THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM
- Upper domination: towards a dichotomy through boundary properties
- Bibliography on domination in graphs and some basic definitions of domination parameters
This page was built for publication: On the computational complexity of upper fractional domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753848)
