@article{oai:niigata-u.repo.nii.ac.jp:00001894,
 author = {Watanabe, Kaoru and Sengoku, Masakazu and Tamura, Hiroshi and Nakano, Keisuke and Shinoda, Shoji},
 issue = {6},
 journal = {IEICE transactions on fundamentals of electronics, communications and computer sciences, IEICE transactions on fundamentals of electronics, communications and computer sciences},
 month = {Jun},
 note = {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.},
 pages = {1222--1227},
 title = {A Scheduling Problem in Multihop Networks},
 volume = {E83-A},
 year = {2000}
}