On Dominating Sets and Independent Sets of Graphs

DOI10.1017/S0963548399004034MaRDI QIDQ4946835zbMATH OpenFDO

Authors Anja Pruchnewski, Margit Voigt, Jochen Harant

Publication date 20 April 2001

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548399004034

zbMATH Keywords

algorithmdominating setsdomination numberindependent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II
• An upper bound for thek-domination number of a graph
• scientific article; zbMATH DE number 3914370
• A note on the k-domination number of a graph
• An algorithm to find two distance domination parameters in a graph
• On approximating the minimum independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• An upper bound for the independent domination number
• On minimum maximal independent sets of a graph
• A note on graphs with largest total k-domination number.

Cited in

(31)

• A lower bound on the independence number of a graph
• Independent 2-point set domination in graphs
• Subexponential fixed-parameter algorithms for partial vector domination
• A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• Independent sets with domination constraints
• Constant thresholds can make target set selection tractable
• New probabilistic upper bounds on the domination number of a graph
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• Combinatorial properties of Farey graphs
• On the complexity of the vector connectivity problem
• On kernelization and approximation for the vector connectivity problem
• On 2-step and hop dominating sets in graphs
• On a polynomial fractional formulation for independence number of a graph
• Restricted domination parameters in graphs
• Continuous dynamical systems that realize discrete optimization on the hypercube
• (Total) vector domination for graphs with bounded branchwidth
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• Subexponential fixed-parameter algorithms for partial vector domination
• Multiple domination
• On vertex independence number of uniform hypergraphs
• Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph
• scientific article; zbMATH DE number 1389216 (Why is no real title available?)
• Independent sets in graphs
• An improvement on the maximum number of k-dominating independent sets
• Dominating Set and Converse Dominating Set of a Directed Graph
• Constructing test functions for global optimization using continuous formulations of graph problems
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
• Complexity of positive influence domination on partial grids
• Weighted domination models and randomized heuristics
• New probabilistic upper bounds on the domination number of a graph. II

This page was built for publication: On Dominating Sets and Independent Sets of Graphs

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