Dominating Sets in Chordal Graphs
From MaRDI portal
Publication:3944643
DOI10.1137/0211015zbMath0485.05055MaRDI QIDQ3944643
J. Howard Johnson, Kellogg S. Booth
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211015
chordal graph; undirected path graphs; minimum dominating set; graph isomorphism problem; directed path graphs; linear time greedy algorithm
Related Items
Dominating cliques in graphs, Total domination in interval graphs, Dominating cliques in graphs, Efficient algorithms for shortest distance queries on special classes of polygons, Domination, independent domination, and duality in strongly chordal graphs, Dominating sets for split and bipartite graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, The weighted perfect domination problem, Improved algorithms and complexity results for power domination in graphs, Combinatorial analysis (nonnegative matrices, algorithmic problems), Counting labelled chordal graphs, Dominating sets and domatic number of circular arc graphs, Clustering and domination in perfect graphs, A linear algorithm for finding a minimum dominating set in a cactus, Some parallel algorithms on interval graphs, On the domatic number of interval graphs, A unified approach to domination problems on interval graphs, Total domination in interval graphs revisited, Labeling algorithms for domination problems in sun-free chordal graphs, Total domination in block graphs, R-domination of block graphs, Chordal graphs and upper irredundance, upper domination and independence, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, Representations of graphs and networks (coding, layouts and embeddings), An optimal algorithm for finding dominating cycles in circular-arc graphs, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, The complexity of domination problems in circle graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, Real and integer domination in graphs, The \(k\)-neighbor, \(r\)-domination problems on interval graphs, Clique tree generalization and new subclasses of chordal graphs, The diversity of domination, Defending the Roman Empire from multiple attacks, Defending the Roman Empire---a new strategy, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, The algorithmic complexity of minus domination in graphs, Tree-decompositions with bags of small diameter, Shiftable intervals, Two algorithms for determining a minimum independent dominating set, On the Algorithmic Complexity of Total Domination, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
