Title :
New scheduling problems in a multi-hop network and their complexity results
Author :
Watanabe, K. ; Tamura, H. ; Sengoku, M.
Author_Institution :
Osaka Electro-Commun. Univ., Japan
Abstract :
The link scheduling problem and broadcast scheduling problem have been discussed as graph theory. These scheduling problems are channels/time-slots assignment problems in a multi-hop network. It is known that the scheduling problems are NP-hard. We propose new extended scheduling problems. These scheduling problems can be applied to CDMA system. We show that the extended scheduling problems are NP-hard.
Keywords :
code division multiple access; computational complexity; graph theory; radio networks; scheduling; CDMA system; NP-hard problems; broadcast scheduling problem; channels assignment problems; graph theory; link scheduling problem; multi-hop network; scheduling problems; time-slots assignment problems; Broadcast technology; Broadcasting; Frequency conversion; Graph theory; Intelligent networks; Multiaccess communication; Relays; Repeaters; Spread spectrum communication; Wireless communication;
Conference_Titel :
Circuits and Systems, 2004. MWSCAS '04. The 2004 47th Midwest Symposium on
Print_ISBN :
0-7803-8346-X
DOI :
10.1109/MWSCAS.2004.1354201
