2023-03-23T16:51:55Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00001894
2022-12-15T03:34:42Z
423:424:425
453:454
A Scheduling Problem in Multihop Networks
A Scheduling Problem in Multihop Networks
Watanabe, Kaoru
6108
Sengoku, Masakazu
6109
Tamura, Hiroshi
6110
Nakano, Keisuke
5597
Shinoda, Shoji
5445
multihop network
mobile communication
graph theory
NP-complete problem
cut covering
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.
journal article
The Institute of Electronics, Information and Communication Engineers
2000-06
application/pdf
IEICE transactions on fundamentals of electronics, communications and computer sciences
6
E83-A
1222
1227
IEICE transactions on fundamentals of electronics, communications and computer sciences
AA10826239
09168508
https://niigata-u.repo.nii.ac.jp/record/1894/files/e83-a_6_1222.pdf
eng
http://www.ieice.org/jpn/trans_online/
copyrightÂ©2000 IEICE