Embedding rectilinear Steiner trees with length restrictions

作者：Mas**erg Jens^*

来源：Theoretical Computer Science, 2016, 654: 59-69.

DOI：10.1016/j.tcs.2016.06.018

• Steiner trees with given topology
• Rectilinear Steiner trees
• Dynamic programming
• Totally unimodular
• Shallow light Steiner trees

We consider the problem of embedding the Steiner points of a Steiner tree with a given topology into the rectilinear plane. Thereby, the length of the path between a distinguished terminal and each other terminal must not exceed given length restrictions. The task is to find an embedding minimizing the total length of the tree.
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.

• 出版日期2016-11-22