2
$\begingroup$

Hello, this is my first post here. I am no mathematician and English is not my first language, so please excuse me if my question is too stupid, it is poorly phrased, or both.

I am developing a program that creates timetables. My timetable-creating algorithm, besides creating the timetable, also creates a graph whose nodes represent each class I have already programmed, and whose arcs represent which pairs of classes should not be programmed at the same time, even if they have to be reprogrammed. The more "heavily linked" a node is, the more inflexible its associated class is with respect to being reprogrammed.

Sometimes, in the middle of the process, there will be no option but to reprogram a class that has already been programmed. I want my program to be able to choose a class that, if reprogrammed, affects the least possible number of other already-programmed classes. That would mean choosing a node in the graph that is "not very heavily linked", subject to some constraints with respect to which nodes can be chosen.

Do you know any algorithms that solve this problem?

$\endgroup$
5
  • 1
    $\begingroup$ Your graph is probably represented as a matrix. Take row or column sums. This gives you the "degrees" of nodes. You want to choose something with the smallest degree. Unless I'm missing something, this is not really a question suited to MO. As such I'm voting to close. $\endgroup$ May 7, 2010 at 23:32
  • $\begingroup$ The number of immediate neighboring nodes is not of my interest. I want a measure that takes into account neighbors of neighbors, neighbors of neighbors of neighbors, etc. possibly with decreasing weight. $\endgroup$
    – isekaijin
    May 7, 2010 at 23:53
  • 1
    $\begingroup$ Then take powers of this matrix. The jkth entry of the nth power gives the number of paths from j to k of length n. Again, row or column sums of this will do the trick. $\endgroup$ May 7, 2010 at 23:59
  • 5
    $\begingroup$ Alternatively, take a lead from Google and work out the eigenvector with largest eigenvalue. That gives you a pretty good measure of which vertices are most linked, taking into account the linking of the neighbours. $\endgroup$
    – gowers
    May 8, 2010 at 12:31
  • $\begingroup$ To generalize @gowers, using the Laplacian and using the eigenvectors to partition the graph gives you a 'sparse cut' which cuts the graph using few edges. There are many variants on this idea - it really depends on what you ultimately want. $\endgroup$ May 8, 2010 at 16:38

2 Answers 2

1
$\begingroup$

I suggest you calculate the shortest path between every two nodes. Several algorithm exist for that:

http://en.wikipedia.org/wiki/Shortest_path

Then you can give each node a value, based on the shortest path to the other nodes. If the shortest paths are longer, it is less heavily connected.

Of course, you can do other solutions as suggested, but I think an important factor in your calculation is whether you may return to your own node or note. If you don't want take into account going back to your own node, you should base it on shortest paths. If you do want to return, then matrix multiplications is the solution, I think.

$\endgroup$
2
$\begingroup$

The best answer I know to that is the pagerank. An intuitive description is the following: the pagerank of a vertex v is approximately the probabilty to end at v when you start at a random vertex and repeatedly pick an edged at random incident to the vertex you are and move to the other extreme of that edge.

The pagerank may be calculated using Nesterov's algorithm. I don't know how fast it will run, but, since it can be done for big data (something like few milions of vertices in a couple hours), I believe it is feasible to compute it instantly for moderate-sized graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.