• DocumentCode
    3569501
  • 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
  • Volume
    2
  • fYear
    2004
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 2004. MWSCAS '04. The 2004 47th Midwest Symposium on
  • Print_ISBN
    0-7803-8346-X
  • Type

    conf

  • DOI
    10.1109/MWSCAS.2004.1354201
  • Filename
    1354201
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3569501