Embedding rectilinear Steiner trees with length restrictions

We show that the problem can be formulated as simple linear programming. Moreover, we analyze the structure of feasible embeddings and give a combinatorial polynomial time algorithm for the problem. Our algorithm combines a dynamic programming approach and binary search and relies on the total unimodularity of a matrix appearing in a sub-problem.1