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 -~----------~----~----~----~------~----~------~--~---
