A linear algorithm for the domination number of a tree
From MaRDI portal
Publication:1219556
DOI10.1016/0020-0190(75)90011-3zbMath0311.68024OpenAlexW2067396114MaRDI QIDQ1219556
S. Goodman, E. J. Cockayne, Stephen T. Hedetniemi
Publication date: 1975
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(75)90011-3
Related Items (91)
On the Algorithmic Complexity of Total Domination ⋮ The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs ⋮ A linear algorithm for finding a minimum dominating set in a cactus ⋮ On the algorithmic complexity of edge total domination ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ The diversity of domination ⋮ Best location of service centers in a treelike network under budget constraints ⋮ On independent \([1, 2\)-sets in trees] ⋮ Induced star partition of graphs ⋮ Combinatorial aspects of the sensor location problem ⋮ On some domination colorings of graphs ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ A polynomial-time approximation to a minimum dominating set in a 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 ⋮ Total domination in block graphs ⋮ A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree ⋮ Covering, Packing and Generalized Perfection ⋮ Mixed Roman domination in graphs ⋮ Laplacian distribution and domination ⋮ On unique minimum dominating sets in some Cartesian product graphs ⋮ A linear time algorithm for optimal \(k\)-hop dominating set of a tree ⋮ Star covers and star partitions of double-split graphs ⋮ A Dynamic Programming Approach to the Dominating Set Problem on k-Trees ⋮ Liar's domination in graphs: complexity and algorithm ⋮ Unnamed Item ⋮ On the vertices belonging to all, some, none minimum dominating set ⋮ Some upper bounds related with domination number ⋮ Algorithmic aspects of the \(k\)-domination problem in graphs ⋮ Towards a new framework for domination ⋮ Independent domination in chordal graphs ⋮ Majorization and the minimum number of dominating sets ⋮ A linear algorithm for secure domination in trees ⋮ R-domination of block graphs ⋮ Dominating sets in perfect graphs ⋮ On minimum dominating sets with minimum intersection ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ On the (M, D) number of a graph ⋮ Computational complexity analysis of the sensor location flow observability problem ⋮ Optimal deadlock resolutions in edge-disjoint reducible wait-for graphs ⋮ Unnamed Item ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Domination cover number of graphs ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Dominating cliques in graphs ⋮ An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model ⋮ On the \(r\)-domination number of a graph ⋮ A note on an induced subgraph characterization of domination perfect graphs ⋮ Constrained domatic bipartition on trees ⋮ Two algorithms for determining a minimum independent dominating set ⋮ Cores of simplicial complexes ⋮ The algorithmic complexity of mixed domination in graphs ⋮ \(\gamma\)-graphs of trees ⋮ Broadcasts and domination in trees ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Dominating cliques in graphs ⋮ Unconditionally secure key assignment schemes ⋮ On the geodetic and geodetic domination numbers of a graph ⋮ Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs ⋮ Minimum dominating cycles in 2-trees ⋮ Domination in distance-hereditary graphs ⋮ An efficient algorithm for distance total domination in block graphs ⋮ \(k\)-power domination in block graphs ⋮ Layered graphs: applications and algorithms ⋮ Optimum domination in weighted trees ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Linear algorithms on recursive representations of trees ⋮ On random trees obtained from permutation graphs ⋮ \(k\)-tuple domination in graphs ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ The Private Neighbor Concept ⋮ Algorithms and Complexity of Power Domination in Graphs ⋮ Unnamed Item ⋮ Algorithmic and complexity aspects of problems related to total Roman domination for graphs ⋮ An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm ⋮ Partitioning trees: Matching, domination, and maximum diameter ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ A linear time algorithm for weighted \(k\)-fair domination problem in cactus graphs ⋮ A linear algorithm for the domination number of a series-parallel graph ⋮ Domination, independent domination, and duality in strongly chordal graphs ⋮ Extensions of the Minimum Dominating Set Problem ⋮ Dominating sets for split and bipartite graphs ⋮ Unique irredundance, domination and independent domination in graphs ⋮ A linear time algorithm for minimum equitable dominating set in trees ⋮ Dominating sets of random recursive trees ⋮ Dominating sets and domatic number of circular arc graphs ⋮ Clustering and domination in perfect graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ An algorithm for the dominator chromatic number of a tree ⋮ The domatic number problem
Cites Work
This page was built for publication: A linear algorithm for the domination number of a tree
