For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Scheduling Problem in Multihop Networks
Kaoru WATANABE Masakazu SENGOKU Hiroshi TAMURA Keisuke NAKANO Shoji SHINODA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/06/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
multihop network, mobile communication, graph theory, NP-complete problem, cut covering,
Full Text: PDF>>
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.