Date: 07/26/05 (Algorithms)    Keywords: web

I'm trying to help a friend in the electrical engineering field out. Their application needs to compute a minimum spanning tree with arbitrary limits on the degree of particular nodes. Plus they insist on certain edges being a part of the solution. I've looked around on the web a bit, sounds like it's an NP problem. If I'm wrong, do let me know! So... any good thoughts on heuristics etc?

My thought was a backtracking algorithm based on Kruskal's (the greedy one), with pruning. Basically you go from shortest to longest. At any edge that could be part of the solution (not create a loop or overload a node), you decide whether to use it. If you say yes all the way, it's effectively Kruskal's, but with the limitations I mentioned. If you remove the degree limitation it *is* Kruskal's.

Anyway, the pruning would be based on estimating the minimum cost of a total solution given the choices you've already made. One way of doing this would be to multiply the number of remaining edges you need by the cost of the current edge, and add on the existing solution vector. If it's greater than your best so far, backtrack.

Oh yeah, any idea how you'd get a tight minimum and maximum limit on the solution cost? A minimum would be Kruskal's without restriction. A maximum... nothing obvious comes to mind. Obviously ANY solution is a maximum, but a tight limit would make for better pruning.

Source: http://www.livejournal.com/community/algorithms/61283.html