What if i want to keep the basic "Strucutre" of the graph intact and still get rid of redundant edges?
On Mar 23, 5:17 pm, "Hadi Moshayedi" <[EMAIL PROTECTED]> wrote: > How about a O(V+E) algorithm? > 1. Find Strongly Connected Components in O(V+E) > 2. Remove those edges (u,v) where component_id[u]==component_id[v] in O(E) > 3. Add edges to graph so vertices in each scc form a cycle in O(V) > > 2008/3/23 Sudhir <[EMAIL PROTECTED]>: > > > > > Does anyone know the answer to this? > > > Given directed graph G = (V, E), explain how to create another graph G > > ′ > > = (V, E′) so that G′ has the same strongly connected components and > > the > > same component graph as G, while keeping E′ as small as possible. > > Describe an algorithm to compute G′ that runs in O(V2 + E) time or > > faster --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
