A Scheduling Problem in Multihop Networks

Kaoru WATANABE; Masakazu SENGOKU; Hiroshi TAMURA; Keisuke NAKANO; Shoji SHINODA

A Scheduling Problem in Multihop Networks

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Keisuke NAKANO, Shoji SHINODA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.6 pp.1222-1227

Publication Date: 2000/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Keisuke NAKANO, Shoji SHINODA, "A Scheduling Problem in Multihop Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 6, pp. 1222-1227, June 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_6_1222/_p

Copy

@ARTICLE{e83-a_6_1222,
author={Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Keisuke NAKANO, Shoji SHINODA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Scheduling Problem in Multihop Networks},
year={2000},
volume={E83-A},
number={6},
pages={1222-1227},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - A Scheduling Problem in Multihop Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1222
EP - 1227
AU - Kaoru WATANABE
AU - Masakazu SENGOKU
AU - Hiroshi TAMURA
AU - Keisuke NAKANO
AU - Shoji SHINODA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2000
AB - 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.
ER -