I have this pseudo-code and I need to understand what it does. It takes some planar graph as input and returns a subset of V (that are the vertexes of the graph). It is clearly recursive, but I don't understand what it does except for the "for" that, I guess, it is a cycle to check the edges starting from 2 vertexes and every time that the condition a=v is satisfied it adds b to a list.
function = function1
input = G(V,E) a planar graph
output = W (a subset of V)
if |V| = 0 then
retrurn {};
end
else
v ∈ V ;
N = {};
for ((a, b) ∈ E or (b, a) ∈ E) do
if a = v then
N = N ∪ {b};
end
end
W1 = {v} ∪ function1(inducedSubgraph(V \ {v}));
W2 = N ∪ function1(inducedSubgraph(V \ {v} \ N));
if |W1| < |W2| then
return W1;
end
else
return W2;
end
end
I suspect it is something about the vertex cover problem, but I'm not sure