0
$\begingroup$

Is there a $O(|V|+|E|)$ algorithm to find and remove all parallel edges in a directed graph? I'm stuck because each idea I've thought of boils down to $deg(v)^2$ comparisons per $v$ which is of course not linear.

Thanks.

$\endgroup$
  • $\begingroup$ Can you define what you mean by "find and remove all parallel edges"? It might help to define what you mean by a "parallel edge", and what you mean by removing all of them. $\endgroup$ – D.W. Feb 12 '18 at 19:13
  • $\begingroup$ How is the graph given to you? $\endgroup$ – Yuval Filmus Feb 12 '18 at 20:47
2
$\begingroup$

Get a list of the edges, this should take no more than $O(|V|+|E|)$ in usual representations.

Run through the edges and check/add them to adjacency matrix represented as hash-table or sparse array. If an edge's entry has been set you know they are parallel. Do some constant time operations during and after iteration to handle the parallel edges how you'd like.

$\endgroup$
0
$\begingroup$

Assuming you mean a directed multigraph...

You can visit each vertex using a depth-first search with edge duplicate detection with a hash table (to avoid infinite cycles). If no cycles, each node gets visited exactly once ~ |V|. If there are cycles, one of the nodes in the cycle may be visited twice ~ <|V|. |V|+<|V|=O(|V|).

In the traversal, if an edge is already in the hash table, delete it (it is a duplicate), otherwise, traverse it and add it to the hash table. There will be exactly |E| duplicate checks and <=|E| traversals. A hash table lookup is O(1) so you get O(|V|+|E|).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.