Labeling algorithms for domination problems in sun-free chordal graphs

DOI10.1016/0166-218X(88)90120-5zbMath0667.05054MaRDI QIDQ1117254

Gerard Jennhwa Chang

Publication date: 1988

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

zbMATH Keywords

algorithmsSteiner tree problemNP-completetotal domination problemk-dominationsun-free chordal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs, The \(k\)-neighbor, \(r\)-domination problems on interval graphs, \(r\)-dominating cliques in graphs with hypertree structure, Approximating the Spanning k-Tree Forest Problem, The weighted perfect domination problem and its variants, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, A linear-time algorithm for semitotal domination in strongly chordal graphs, Algorithmic Aspects of Disjunctive Total Domination in Graphs, Liar's domination in graphs: complexity and algorithm, The weighted perfect domination problem, Domination and total domination on asteroidal triple-free graphs, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, On total \(f\)-domination: polyhedral and algorithmic results, Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Complexity of distance paired-domination problem in graphs, Paired-domination problem on distance-hereditary graphs, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, Hardness results and approximation algorithm for total liar's domination in graphs, A linear-time algorithm for paired-domination problem in strongly chordal graphs, Domination in distance-hereditary graphs, A survey of selected recent results on total domination in graphs, An efficient algorithm for distance total domination in block graphs, Chromatic numbers of competition graphs, \(k\)-tuple domination in graphs, Weighted connected domination and Steiner trees in distance-hereditary graphs, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• A linear algorithm for finding a minimum dominating set in a cactus
• Total domination in block graphs
• R-domination of block graphs
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• A linear algorithm for the domination number of a tree
• A linear algorithm for the domination number of a series-parallel graph
• Covering, Packing and Generalized Perfection
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• 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
• R -Domination in Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The NP-completeness column: An ongoing guide
• Total domination in interval graphs