Analysis of a greedy heuristic for finding small dominating sets in graphs

DOI10.1016/0020-0190(91)90021-9zbMath0746.05061OpenAlexW2151624738MaRDI QIDQ1183397

Abhay K. Parekh

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90021-9

zbMATH Keywords

dominating setsgreedy heuristic

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

On parallelizing a greedy heuristic for finding small dominant sets ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Heuristics for \(k\)-domination models of facility location problems in street networks ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ Data Exploration by Representative Region Selection: Axioms and Convergence ⋮ On the distribution of the domination number for random class cover catch digraphs ⋮ The greedy algorithm for domination in graphs of maximum degree 3 ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ Classification using proximity catch digraphs ⋮ Characterizing the scale dimension of a high-dimensional classification problem

Cites Work

• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Analysis of a greedy heuristic for finding small dominating sets in graphs