|
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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83-A
No.6
pp.1222-1227 Publication Date: 2000/06/25 Online ISSN:
DOI: Print ISSN: 0916-8508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: multihop network, mobile communication, graph theory, NP-complete problem, cut covering,
Full Text: PDF>>
Summary:
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.
|
|
|