版权所有：内蒙古大学图书馆 技术提供：维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
ANALYSIS OF A GREEDY HEURISTIC FOR FINDING SMALL DOMINATING SETS IN GRAPHS
作者机构：Laboratory for Information and Decision Systems M.I.T. Cambridge MA 02139 USA
出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)
年 卷 期：1991年第39卷第5期
页 面：237-240页
核心收录：
学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）]
主 题：ANALYSIS OF ALGORITHMS APPROXIMATE ALGORITHMS
摘 要：We analyze a simple greedy algorithm for finding small dominating sets in undirected graphs of N nodes and M edges. We show that d(g) less-than-or-equal-to N + 1 - square-root 2 M + 1, where d(g) is the cardinality of the dominating set returned by the algorithm.
