A Scheduling Problem in Multihop Networks

概要

論文の詳細を見る
In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V, A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u, v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u, v) ≐̸ f(v, w) for any adjacent arcs (u, v) and (v, w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.
社団法人電子情報通信学会の論文
2000-06-25