On minimum dominating sets with minimum intersection

DOI10.1016/0012-365X(90)90364-NzbMath0745.05057MaRDI QIDQ1174139

Peter J. Slater, Dana L. Grinstead

Publication date: 25 June 1992

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

minimum dominating sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items

Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ On minimum intersection of two minimum dominating sets of interval graphs ⋮ Pairs of disjoint dominating sets and the minimum degree of graphs ⋮ Remarks about disjoint dominating sets ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Linear time algorithms for NP-hard problems restricted to partial k- trees
• R-domination of block graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A linear algorithm for the domination number of a tree
• Some simplified NP-complete graph problems
• A linear algorithm for the domination number of a series-parallel graph
• The NP-completeness column: an ongoing guide
• Graph minors. II. Algorithmic aspects of tree-width
• Linear-time computability of combinatorial problems on series-parallel graphs
• R -Domination in Graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• The complexity of satisfiability problems
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item