A linear algorithm for finding a minimum dominating set in a cactus
From MaRDI portal
Publication:1078205
DOI10.1016/0166-218X(86)90089-2zbMath0596.05051OpenAlexW2008228846MaRDI QIDQ1078205
John Pfaff, Renu C. Laskar, Stephen T. Hedetniemi
Publication date: 1986
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(86)90089-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (22)
On the algorithmic complexity of edge total domination ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ One-node cutsets and the dominating set polytope ⋮ SIGNED STAR DOMINATION IN GRAPHS ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Unnamed Item ⋮ On the dominating set polytope ⋮ Algorithmic aspects of the \(k\)-domination problem in graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ The obnoxious center problem on weighted cactus graphs. ⋮ Unnamed Item ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Broadcasting on cactus graphs ⋮ Integer programming approach to static monopolies in graphs ⋮ Unnamed Item ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ An efficient algorithm for distance total domination in block graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Graphs with unique dominating sets ⋮ Unnamed Item ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
Cites Work
This page was built for publication: A linear algorithm for finding a minimum dominating set in a cactus
