Could you please explain the question. Typically in a directed graph we talk of in-degree and out-degree for a vertex. So is the question then to minimize the maximum of these in all vertices of the graph? If so what operations are permitted?
On 5/16/07, pramod <[EMAIL PROTECTED]> wrote: > > 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 > > > > > -- Regards, Rajiv Mathews --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
