文章基本信息

标题：ROUTING ALGORITHMS UNDER MUTUAL INTERFERENCE CONSTRAINTS
本地全文：下载
作者：Kota Ishihara ; Yusuke Kobayashi
期刊名称：日本オペレーションズ・リサーチ学会論文誌
印刷版ISSN：0453-4514
电子版ISSN：2188-8299
出版年度：2015
卷号：58
期号：3
页码：209-222
DOI：10.15807/jorsj.58.209
出版社：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.