Approximate vertex cover problem

2013 11 12
2 个回答
回答已采纳
更新时间：2013 11 30
6 次查看（30 天）

0 个投票

Hello, I have 2 question: I want you resolve Approximate vertex cover problem, therefore
1.Can someone give me function who will choice random edge(2 vertex, ex: u and v) in graph, 2.And then function who will delete all egdes incident on either u and v.
Thank you!

请先登录，再回答此问题。

 采纳的回答

Ben Petschel
Ben Petschel 2013-11-15

0 个投票

Assuming you've got an incidence matrix A with A(u,v) if there is an edge from u to v, then a random edge could be selected with
i = randsample(find(A),1);
[u,v] = ind2sub(size(A),i);
and then delete the edges with
A(u,:) = 0; % edges from u
A(:,u) = 0; % edges to u
A(v,:) = 0;
A(:,v) = 0;
This is probably not the most efficient algorithm but if the number of vertices is large then it should run a lot faster if you make A a sparse array.

更多回答（1 个）

Ivan
Ivan 2013-11-15
编辑：Ivan 2013-11-30

0 个投票

Thank you, but [u,v] should be two adjacent vertices, and ind2sub don't do that. ind2sub do right for v, but for u he backs size of edges.

类别

在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by