When will your algorithm stop ? It is unlikely to reverse only once and get the optimal.
On May 17, 4:07 am, pramod <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
