Ohh, sorry to have missed that information. Consider minimizing the maximum out-degree.
On May 16, 5:04 pm, "Rajiv Mathews" <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
