出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：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.
