10
$\begingroup$

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. enter image description here

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

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.

enter image description here

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

I don't have a solution to your problem, but I've got an intermediate simplification. Constraint 2 (each splitter node $i$ is allowed to split one wire into no more than $k_i$ wires) is what has me stumped.

The simplification is that you can eliminate all the intermediate (square) nodes. Create a graph with just the source node, the sink nodes, and the splitter nodes.

  1. In your original graph find the shortest path from the source node to each splitter node and add an edge in the new graph from the source node to the splitter node with that length.

  2. Given two splitter nodes, $i$ and $j$ find the shortest path from $i$ to $j$ in the original graph and add an edge in the new graph from $i$ to $j$ with that length.

  3. For every splitter $i$ and every sink $j$ find the shortest path from $i$ to $j$ in the original graph and add an edge in the new graph from $i$ to $j$ with that length.

Now you have a fully connected graph of $N$ splitters, (plus the source and the sinks). The edges have costs and you are trying to find a minimum cost tree that satisfies the constraint that each splitter node $i$ has no more than $k_i$ children.

This (reduced) problem seems harder than the degree-constrained minimum spanning tree problem, which is NP-hard, because there is a different degree $k_i$ on each node rather than a single degree constraint. But it is also different because you aren't actually looking for a spanning tree. Rather the desired minimum tree can leave out some of the splitter nodes. I don't know whether this second difference makes the problem easier or harder.

$\endgroup$
  • $\begingroup$ If you only want a subset of the graph to be connected, then this is the Steiner tree problem. $\endgroup$ – Chao Xu Nov 16 '13 at 8:17
0
$\begingroup$

@Chao Xu, I also found Steiner to be nearest approximation to my problem. I am exploring Ant based systems to solve this problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.