Title :
Graph problems in multi-hop networks
Author :
Watanabe, K. ; Sengoku, M. ; Tamura, H. ; Nakano, K. ; Shinoda, S.
Author_Institution :
Osaka Electro-Commun. Univ., Neyagawa, Japan
Abstract :
In a multihop network, radio packets are often relayed through inter-mediate nodes (repeaters) in order to transfer a message. We consider a scheduling problem in a multihop network using two graph theoretical models. In this report, we prove that this problem is NP-hard, and we propose approximation algorithms for it
Keywords :
graph theory; radio networks; scheduling; NP-hard problem; approximation algorithm; graph theory; message transfer; multi-hop network; radio packet; repeater; scheduling; Approximation algorithms; Frequency division multiaccess; Graph theory; Intelligent networks; Labeling; Multiaccess communication; Relays; Repeaters; Spread spectrum communication; Time division multiple access;
Conference_Titel :
Circuits and Systems, 2001. ISCAS 2001. The 2001 IEEE International Symposium on
Conference_Location :
Sydney, NSW
Print_ISBN :
0-7803-6685-9
DOI :
10.1109/ISCAS.2001.922382
