Approximate vertex cover problem

Question

Ivan 2013-11-12

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/105846-approximate-vertex-cover-problem

编辑： Ivan 2013-11-30

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!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Ben Petschel 2013-11-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/105846-approximate-vertex-cover-problem#answer_115301

在 MATLAB Online 中打开

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.