R -Domination in Graphs

DOI10.1145/321958.321964zbMath0349.05120OpenAlexW2022548094MaRDI QIDQ4119239

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321958.321964

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items

Domination with decay in triangular matchstick arrangement graphs, The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs, On independent \([1, 2\)-sets in trees], Optimal broadcast domination in polynomial time, A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph, Approximating the Spanning k-Tree Forest Problem, Labeling algorithms for domination problems in sun-free chordal graphs, The weighted perfect domination problem and its variants, An algorithm to find two distance domination parameters in a graph, On orthogonally guarding orthogonal polygons with bounded treewidth, Matchings and transversals in hypergraphs, domination and independence in trees, Total domination in block graphs, Distance domination in graphs with given minimum and maximum degree, A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree, Covering, Packing and Generalized Perfection, A linear time algorithm for optimal \(k\)-hop dominating set of a tree, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Distance domination of generalized de Bruijn and Kautz digraphs, Unnamed Item, Domination and location in acyclic graphs, Unnamed Item, Independent domination in chordal graphs, R-domination of block graphs, On minimum dominating sets with minimum intersection, Optimal \((t, r)\) broadcasts on the infinite grid, An Algorithm for the Inverse Distance-2 Dominating Set of a Graph, An optimal algorithm to find minimum k-hop dominating set of interval graphs, On the computational complexity of centers locating in a graph, On the \(r\)-domination number of a graph, Some new results on distance \(k\)-domination in graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Unnamed Item, Minimum dominating cycles in 2-trees, Domination in distance-hereditary graphs, An efficient algorithm for distance total domination in block graphs, Center location problems on tree graphs with subtree-shaped customers, Total domination in graphs, \(k\)-tuple domination in graphs, Efficient parallel algorithms for r-dominating set and p-center problems on trees, Distance Domination in Graphs, Statistical mechanics of the directed 2-distance minimal dominating set problem, Efficient \(( t , r )\) broadcast dominating sets of the triangular lattice, Weighted connected domination and Steiner trees in distance-hereditary graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Unnamed Item, Vertex fusion under distance constraints, Domination with exponential decay, Domination, independent domination, and duality in strongly chordal graphs, Mim-width. III. Graph powers and generalized distance domination problems, Dominating sets for split and bipartite graphs, Linear programming formulation for some generalized domination parameters, Broadcasts in graphs, On \((t,r)\) broadcast domination numbers of grids, Dominating sets and domatic number of circular arc graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, The domatic number problem