g*******y
发帖数: 1930 | 1 看了一晚上精华区，发现这道题有问题啊。
5。Given a graph (any type - Directed acyclic graph or undirected graphs
with loops), find a minimal set of vertices which affect all the edges of
the graph.
An edge is affected if the edge is either originating or terminating from
that vertex.
The time should be less Q(n^2)
这个题就是最小顶点覆盖问题吧？
或者是我对最小顶点覆盖问题理解有误？或者对这题理解有误？ |
p*********a
发帖数: 21 | 2 图论, 最小顶点复盖, 随便找个二分图匹配的算法就可以解决. "The time should be less Q(n^2)"---不过稠密图有小于O(n^2)的二分匹配算法么? |
g*******y
发帖数: 1930 | 3 对啊，这个是NPC啊，O(n^2)做出来了，还用找工作？？？
be less Q(n^2)"---不过稠密图有小于O(n^2)的二分匹配算法么?
【在 p*********a 的大作中提到】
: 图论, 最小顶点复盖, 随便找个二分图匹配的算法就可以解决. "The time should be less Q(n^2)"---不过稠密图有小于O(n^2)的二分匹配算法么?
|
p*********a
发帖数: 21 | 4 这个有O(n^2)的和O(sqrt(n)*e)的算法, 我是说没有复杂度小于O(n^2)的算法
【在 g*******y 的大作中提到】
: 对啊，这个是NPC啊，O(n^2)做出来了，还用找工作？？？
:
: be less Q(n^2)"---不过稠密图有小于O(n^2)的二分匹配算法么?
|
Z*****Z
发帖数: 723 | 5 小尾羊这题最后什么结论啊？
【在 g*******y 的大作中提到】
: 看了一晚上精华区，发现这道题有问题啊。
: 5。Given a graph (any type - Directed acyclic graph or undirected graphs
: with loops), find a minimal set of vertices which affect all the edges of
: the graph.
: An edge is affected if the edge is either originating or terminating from
: that vertex.
: The time should be less Q(n^2)
: 这个题就是最小顶点覆盖问题吧？
: 或者是我对最小顶点覆盖问题理解有误？或者对这题理解有误？
|
