支配集贪婪逼近最坏情况例子
Pat*_*idt 4 math graph discrete-mathematics graph-algorithm
要找到无向图G的最小支配集,您可以使用如下的贪婪算法:从空集开始D.直到D是支配集,添加具有最大数量的未覆盖邻居的顶点v.
该算法通常没有找到最优解,它是ln(Delta) - 近似.(如果Delta是G中顶点的最大度数)
现在我正在寻找一个简单的例子,其中贪婪算法找不到最佳解决方案.我找到的唯一一个是集合覆盖问题的相关实例.(http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm图片右侧)将此图片转换为图表将导致至少14个顶点和大量边缘.
有谁知道一个小例子？
提前致谢
