Dominating sets in perfect graphs

DOI10.1016/0012-365X(90)90357-NzbMath0746.05066OpenAlexW2073365610MaRDI QIDQ1174132

Lorna K. Stewart, Derek Gordon Corneil

Publication date: 25 June 1992

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

Full work available at URL: https://doi.org/10.1016/0012-365x(90)90357-n

zbMATH Keywords

perfect graphsdominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items

Total domination and transformation, On the feedback vertex set problem in permutation graphs, Dominations in trapezoid graphs, Connected domination and steiner set on asteroidal triple-free graphs, Some advances on the set covering polyhedron of circulant matrices, Revisiting \(k\)-tuple dominating sets with emphasis on small values of \(k\), One-node cutsets and the dominating set polytope, Labeling algorithms for domination problems in sun-free chordal graphs, On dominating set polyhedra of circular interval graphs, Weighted domination of cocomparability graphs, Incomparability graphs of the lattices \(L_{n}\) and \(L_n^{1^2}\), Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals, Domination and total domination on asteroidal triple-free graphs, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs, The complexity of domination problems in circle graphs, Paired-domination problem on distance-hereditary graphs, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, A survey of selected recent results on total domination in graphs, Weighted connected domination and Steiner trees in distance-hereditary graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Domination, independent domination, and duality in strongly chordal graphs
• Dominating sets for split and bipartite graphs
• Weakly triangulated graphs
• Finding minimum dominating cycles in permutation graphs
• Clustering and domination in perfect graphs
• Hamiltonian circuits in interval graph generalizations
• On domination problems for permutation and other graphs
• A unified approach to domination problems on interval graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Independent domination in chordal graphs
• Permutation graphs: Connected domination and Steiner trees
• A linear algorithm for the domination number of a tree
• On the Algorithmic Complexity of Total Domination
• Steiner trees, connected domination and strongly chordal graphs
• Domination in permutation graphs
• The NP-completeness column: an ongoing guide
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Dominating Sets in Chordal Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs
• Total domination in interval graphs
• Total domination in interval graphs
• 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