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.