1
$\begingroup$

I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix: $$ \left[ \begin{array}{c} - & A & B & C & D & E & F \\ A & 0 & 120 & 100 & inf & inf & 30 \\ B & 120 & 0 & 70 & inf & 150 & inf \\ C & 100 & 70 & 0 & 60 & 60 & inf \\ D & inf & inf & 60 & 0 & inf & 50 \\ E & inf & 150 & 60 & inf & 0 & inf \\ F & 30 & inf & inf & 50 & inf & 0 \\ \end{array} \right] $$ Prim's algorithm will result in something like this: $$ \left[ \begin{array}{c} - & A & B & C & D & E & F \\ A & 0 & inf & inf & inf & inf & 30 \\ B & inf & 0 & 70 & inf & inf & inf \\ C & inf & 70 & 0 & 60 & 60 & inf \\ D & inf & inf & 60 & 0 & inf & 50 \\ E & inf & inf & 60 & inf & 0 & inf \\ F & 30 & inf & inf & 50 & inf & 0 \\ \end{array} \right] $$

However, node A is now zoned and it will take at least 3 transitions from $A$ to get to $C$ and for my specific CSP I need at most 2 transitions. It is fairly easy to incorporate such CSP into Prim's algorithm. The question is: are there any generic algorithms which deal with finding a minimal spanning tree given a set of constraints ?

$\endgroup$
  • $\begingroup$ What do you mean with CSP exactly here? $\endgroup$ – Juho Apr 7 '13 at 14:09
  • $\begingroup$ Please state in general, formal terms what the additional restrictions are. $\endgroup$ – Raphael Apr 7 '13 at 14:13
  • $\begingroup$ Edited the question. $\endgroup$ – Denys S. Apr 7 '13 at 14:44
  • $\begingroup$ Perhaps this might be releted to your question en.wikipedia.org/wiki/Steiner_tree_problem $\endgroup$ – fidbc Apr 7 '13 at 14:52
  • $\begingroup$ What kind of constraints do you have in mind? You will have to be specific. It might be that certain kinds of constraints lead to problem we don't know how to solve efficiently. $\endgroup$ – Juho Apr 7 '13 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.