
For FullText 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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.6
pp.12221227 Publication Date: 2000/06/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: multihop network, mobile communication, graph theory, NPcomplete problem, cut covering,
Full Text: PDF(589.1KB)>>
Summary:
In a multihop network, radio packets are often relayed through intermediate 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 antitransitivelabeling problem is the problem of finding a minimum antitransitivelabeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NPhard, and we propose a simple distributed approximation algorithm for it.

