A scheduling problem in multihop networks

In a multihop network, radio packets are of ten relayed through inter-media te stations (repenters) in order to transfer a radio packet from a source t o its destination. We consider a scheduling problem in a multihop network u sing a graphtheoretical model. Let D = (V, A) be the digraph with a vertex set V and an are set A. Let f be a labeling of positive integers on the arc s of A. The value of f(u, v) means a frequency band assigned on the link fr om u to v. We call f antitransitive if S(u, v) not equal f(v, w) for any ad jacent arcs (u, v) and (v, w) of D. The minimum antitransitive-labeling pro blem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. I n this paper, we prove that this problem is NP-hard, and we propose a simpl e distributed approximation algorithm for it.