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:
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:
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