Need some help understanding this problem about maximizing graph connectivity

Posted by Legend on Stack Overflow See other posts from Stack Overflow or by Legend
Published on 2010-05-10T21:17:05Z Indexed on 2010/05/10 21:34 UTC
Read the original article Hit count: 312

I was wondering if someone could help me understand this problem. I prepared a small diagram because it is much easier to explain it visually.

alt text

Problem I am trying to solve:

1. Constructing the dependency graph Given the connectivity of the graph and a metric that determines how well a node depends on the other, order the dependencies. For instance, I could put in a few rules saying that

  • node 3 depends on node 4
  • node 2 depends on node 3
  • node 3 depends on node 5

But because the final rule is not "valuable" (again based on the same metric), I will not add the rule to my system.

2. Execute the request order Once I built a dependency graph, execute the list in an order that maximizes the final connectivity. I am not sure if this is a really a problem but I somehow have a feeling that there might exist more than one order in which case, it is required to choose the best order.

First and foremost, I am wondering if I constructed the problem correctly and if I should be aware of any corner cases. Secondly, is there a closely related algorithm that I can look at? Currently, I am thinking of something like Feedback Arc Set or the Secretary Problem but I am a little confused at the moment. Any suggestions?

PS: I am a little confused about the problem myself so please don't flame on me for that. If any clarifications are needed, I will try to update the question.

© Stack Overflow or respective owner

Related posts about language-agnostic

Related posts about algorithm