支配集贪婪近似最坏情况示例 [英] Dominating Set Greedy Approximation Worst-Case Example

问题描述

要找到无向图G的最小控制集，可以使用如下贪婪算法:从一个空的集合D开始.直到D是一个主导集合，然后添加一个顶点v，该顶点v的未覆盖邻居数量最大.

To find a minimum Dominating Set of an undirected Graph G you can use a greedy algorithm like this: Start with an empty set D. Until D is a dominating Set, add a vertex v with maximum number of uncovered neighbours.

该算法通常找不到最佳解，它是lnΔ近似值.(如果Delta是G中顶点的最大程度)

The algorithm generally does not find the optimal solution, it is a ln(Delta)-approximation. (If Delta is the maximum degree of a vertex in G)

现在，我正在寻找一个简单的示例，其中贪心算法无法找到最佳解决方案.我发现的唯一一个是布景问题的相关实例.(<正确的)将其转换为图形将至少产生14个顶点和许多边.

Now I am looking for a simple example where the greedy algorithm does not find the optimal solution. The only one I found is a related instance of the set cover problem. (http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm picture on the right) Translating this one to a graph would cause a minimum of 14 vertices and a lot of edges.

有人知道一个小例子吗?

Does anyone know a small example?

预先感谢

推荐答案

请考虑以下图形:

贪婪的方法将选择B，然后选择D和G.同时，E和F形成一个主导集.

A greedy approach will choose B then D and G. Meanwhile, E and F form a dominating set.

这篇关于支配集贪婪近似最坏情况示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！