Independent domination in chordal graphs

DOI10.1016/0167-6377(82)90015-3zbMath0495.05053OpenAlexW2037637265MaRDI QIDQ1169487

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90015-3

zbMATH Keywords

independent set dominating set chordal graphs

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (48)

Generating all maximal independent sets on trees in lexicographic order ⋮ On the independent dominating set polytope ⋮ The weighted independent domination problem is NP-complete for chordal graphs ⋮ Convexity in Graphs and Hypergraphs ⋮ On the kernelization of split graph problems ⋮ An Analogue of the Shannon Capacity of a Graph ⋮ Weighted domination of cocomparability graphs ⋮ More results on weighted independent domination ⋮ Roman domination on strongly chordal graphs ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ Independent domination in finitely defined classes of graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Bounds on 2-point set domination number of a graph ⋮ Perfect domination and small cycles ⋮ Roman domination in graphs. ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ Independent dominating set problem revisited ⋮ Counting the number of independent sets in chordal graphs ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ The complexity of domination problems in circle graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Intersection graphs of non-crossing paths ⋮ Improved bottleneck domination algorithms ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Independent domination versus weighted independent domination ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ On approximating the minimum independent dominating set ⋮ Laminar structure of ptolemaic graphs with applications ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ Mind the independence gap ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ Domination, independent domination, and duality in strongly chordal graphs ⋮ Linear programming approach for various domination parameters ⋮ Linear programming formulation for some generalized domination parameters ⋮ Independent Domination in Triangle Graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Well-covered graphs and extendability

Cites Work

This page was built for publication: Independent domination in chordal graphs