I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner tree – e.g. http://www.cs.umd.edu/~samir/grant/gk98b.ps.

I have a number of connectors which have a fixed location in space and are connected together by wires. This can be represented as a graph where the connectors are nodes and the wires are edges:

Original layout

Each wire needs to be surrounded by a tube to protect it and a tube can contain many wires. Two or more tubes can be joined together at a junction. In the sketch below, the black lines show the outside of the tubes and the grey circles show junctions, but with each connector still connected by the same wires as before:

Layout showing junctions and tubes

Both the tubes and the junctions have a cost associated with them – for the tubes this is proportional to the length of the tube, for the junctions this is a fixed cost per junction. For example, if the tubes cost \$10 per metre and the junctions cost \$5 each, 1 metre of tubes with two junctions would be 10 + 5 + 5 = \$20.

I would like to find a layout that minimises the cost of the total length of tube + the cost of the junctions. I don’t think it’s quite the same problem as the reference above – I need to ensure that that the wires connecting between the connectors do not change, only the intermediate junctions between them. My real application has approximately 300 nodes and 1500 edges.



  • $\begingroup$ Have you started by reviewing the literature on Euclidean Steiner trees? e.g., en.wikipedia.org/wiki/Steiner_tree_problem $\endgroup$ – D.W. Mar 17 '14 at 21:46
  • $\begingroup$ Yes, I've found a lot of papers on both Euclidean trees (which deal with positioning the additional junctions to minimise edge length) and node-weighting (dealing with the cost of the junctions). I'm hopeful my problem will be handled by a small modification to one of these algorithms. I guess I was hoping that someone would recognise this exact problem as something that had been solved before and point me at a solution - I'm slightly worried that finding an algorithm that works is going to take me more than a day or so, in which case I would rather stop trying now! $\endgroup$ – Rich Nicholson Mar 18 '14 at 9:45

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.