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>>
Buy this Article


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.