ROUTING ALGORITHMS UNDER MUTUAL INTERFERENCE CONSTRAINTS
Kota Ishihara, Yusuke Kobayashi · Journal of the Operations Research Society of Japan · 2015
In wireless sensor networks, transportation networks, or VLSI-layout, routing is a fundamental problem and it can be modeled as finding paths with some conditions in a given graph. Among such types of problems, finding disjoint paths connecting given terminal pairs is called the disjoint paths problem, and it is well-studied in the fields of theoretical computer science and graph algorithms. In this paper, we consider a problem of finding paths that are not only disjoint but also “far” from each other, which aims at reducing mutual interference among paths. Our theoretical contribution is to give polynomial time algorithms for some cases of this problem. We also propose a solution based on the integer programming, which can be applied to many kinds of routing problems.