[Solved]: Wiring Length Minimization

Problem Detail: 

My Problem is like this:

1. I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where wire can go.

2. There are some special Nodes, called splitters, from where a single wire can be splitted to 2 or more up to k. The k can be taken constant for now but it varies from node to node. Not all nodes are splitters.

3. There is one source of power from where a wire will emerge. It is the source. The wire has to be taken to n sinks.

4. An edge can take any number of wires traversing through it in either direction.

5. The the total wire length has to be minimized.

6. The nature of graph, planar or euclidean is not known.

Example: Below is a sample network. Nodes are named as numbers and edges are provided with equal weights of 1. Source is Node1 and Sinks are Node5, Node9 and Node13. In case 1 Node6 is Splitter node. In case 2 Node6 and Node4 are splitter nodes. The splitter node's k=3, i.e., it can take in one wire and split it out to 3 wires.

Case 1. Only one splitter Node. It makes sense to split at Node6.

Case 2. Two splitter Node. It makes sense to split at Node4 instead of Node6.

I am looking for different strategies to find out a generic solution for this problem. The graph presented here is of a smaller scale as compared to the problem in hand. The graph is static and can not be changed (i mean the solution should not suggest any new edge or propose new splitter location ). Any reference to research paper published on this kind of problem is also welcomed.

Case 3. Two splitter Node. It makes sense to split at Node4 and Node14. Note that this case has edge weights changed for Edge 8-12, 6-10 and 10-11. The important thing in this case is retracing of a wire after getting splitted from Node14.

Asked By : Mohitt

Answered By : Chao Xu

This problem is NP-hard.

Assume every vertex is a splitter that can split to any number of degrees, then your problem is precisely the Steiner tree problem on a graph, where the set of source and sink vertices are the required vertices.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18041

 Ask a Question

 Download Related Notes/Documents