3
$\begingroup$

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.

Thanks,

Rich

|cite|improve this question
$\endgroup$
  • $\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.