2024-03-29T05:33:43Z
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
Sengoku, Masakazu
Tamura, Hiroshi
Nakano, Keisuke
Shinoda, Shoji
copyright©2000 IEICE
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.
The Institute of Electronics, Information and Communication Engineers
2000-06
eng
journal article
http://hdl.handle.net/10191/6530
https://niigata-u.repo.nii.ac.jp/records/1894
http://www.ieice.org/jpn/trans_online/
AA10826239
09168508
IEICE transactions on fundamentals of electronics, communications and computer sciences
IEICE transactions on fundamentals of electronics, communications and computer sciences
E83-A
6
1222
1227
https://niigata-u.repo.nii.ac.jp/record/1894/files/e83-a_6_1222.pdf
application/pdf
606.3 kB
2019-07-29