Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let us have a graph. When we remove an edge, 2 'cars' are created, one from each vertice of the edge. when these 2 cars meet they stop. The problem is to create a spanning tree so that the sum of the numbers of cars that pass through each vertice is minimal.

The added difficulty is that if a vertice has n cars passing from it, then the cost is K^n and not n*K.

some thoughts. We could find the shortest chordless cycles as a start but the position of those chordless cycles, ie whether they touch each other, changes the metric and thus what the shortest cycle is.

This is not a minimum spanning tree problem. I want to solve this because each car represents a varriable and the spanning tree is the most efficient way to compute an optimization problem. When 2 cars from the same edge meet and stop, I have a reduction of one varriable from the optimization.


The process is like this. We remove a number of edges to make the graph a spanning tree. Each removed edge creates 2 cars, one at each vertice of the removed edge, that need to meet each other. We fix a path for each of those twin cars. We then check how many cars (from all the edges that we removed) pass through each vertice. If the number of the cars that pass from a vertice is n, the cost is K^n where K is a constant. We then add all the costs and that is the global cost that needs to be minimized.

please tell me if something is unclear.

share|improve this question
@Apostolis: You might rewrite your problem description in your first paragraph. I cannot understand what you are asking. –  Joseph O'Rourke Jan 21 '12 at 15:10
Something that I think was unclear is the fact that removing an edge creates the twin cars. –  Apostolis Xekoukoulotakis Jan 21 '12 at 17:54
It is also unclear when the cars start and where they are supposed to go. If you can pick tthe direction arbitrarily after the tree is formed, find as close to a perfect matching in the tree as you can and send those cars into one another. That shows that you want to have the tree composed of paths Pk where k is even. Gerhard "Ask Me About System Design" Paseman, 2012.01.21 –  Gerhard Paseman Jan 21 '12 at 18:20
The time is irrelevant since we count how many cars pass through each vertice, concurrency is not required. The starting point of each car is fixed based on the edge you removed. So is the position of its twin car, or anticar. Since those 2 cars need to meet, after you create the spanning tree, it seems that there will be only one route to choose, so what you do is simmply check the path that the spanning tree allows them to take. –  Apostolis Xekoukoulotakis Jan 21 '12 at 19:07
There are 2 problems then. 1> When you remove one edge, you restric the routes that the other cars can take to meet their 'anticar'. 2> Removing the edge also creates 2 twin cars. One strategy is this. 1> You find the number d of edges that are needed to be removed. 2> You pick d of the shortest chordless cycles which as a sum contain all the edges and vertices of the graph. You try to find the shortest cycles that dont have many edges in common. 3>You remove one edge from each chordless cycle, the one which is the least common between them. –  Apostolis Xekoukoulotakis Jan 21 '12 at 19:22
show 5 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.