Here's a graph problem. We are given a directed graph. We are allowed to change the directions of the edges. Our aim is to minimize the maximum degree in the graph. How do we achieve this?
One way is to take the vertex with maximum degree, and take another vertex with least degree reachable from this max-degree vertex and then reverse all the edges' direction along the path. Now the questions with this approach are (1) how do we prove that this will lead to the optimal-graph in the sense, can we get a graph such that it's maximum degree is the best possible? (2) What's the time complexity, is it bound tightly? (3) Is there any better way? Thanks --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
