A scheduling problem in multihop networks
In a multihop network, radio packets are of ten relayed through inter-mediate stations (repenters) 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 are 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 S(u, v) not equal 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.
multihop network mobile communication graph theory np-complete problem cut covering