咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >ANALYSIS OF A GREEDY HEURISTIC... 收藏

ANALYSIS OF A GREEDY HEURISTIC FOR FINDING SMALL DOMINATING SETS IN GRAPHS

作     者:PAREKH, AK 

作者机构: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分