On Dominating Sets and Independent Sets of Graphs

DOI10.1017/S0963548399004034zbMath0959.05080MaRDI QIDQ4946835

Anja Pruchnewski, Margit Voigt, Jochen Harant

Publication date: 20 April 2001

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

zbMATH Keywords

algorithmindependent setdomination numberdominating sets

Mathematics Subject Classification ID

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

Related Items (23)

(Total) vector domination for graphs with bounded branchwidth ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ On kernelization and approximation for the vector connectivity problem ⋮ On 2-step and hop dominating sets in graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph ⋮ On a polynomial fractional formulation for independence number of a graph ⋮ Independent sets in graphs ⋮ Restricted domination parameters in graphs ⋮ Constructing test functions for global optimization using continuous formulations of graph problems ⋮ 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 ⋮ Constant thresholds can make target set selection tractable ⋮ Continuous dynamical systems that realize discrete optimization on the hypercube ⋮ Multiple Domination ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ 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 ⋮ A lower bound on the independence number of a graph ⋮ Combinatorial properties of Farey graphs ⋮ On the complexity of the vector connectivity problem

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