@article{Nofal2024, 
author = {Samer Nofal},
title = {On the time complexity of achieving optimal throughput in time division multiple access communication networks},
year = {2024},
journal = {AIMS Mathematics},
volume = {9},
number = {5},
pages = {13522-13536},
keywords = {time complexity, expected depth of recursion tree, exact scheduling, optimal throughput, time division multiple access, communication networks},
url = {https://www.sciopen.com/article/10.3934/math.2024659},
doi = {10.3934/math.2024659},
abstract = {The fundamental problem of finding transmission schedules for achieving optimal throughput in time division multiple access (TDMA) communication networks is known to be NP-hard. Let        N   be a scheduled    k-time slot TDMA network with    n stations and    m links. We showed that an optimal link schedule for        N   can be computed recursively with a recursion tree of logarithmic depth        O    (  ln  ⁡  m  ) in expectation. Additionally, we showed that optimal link schedules for those TDMA networks, with recursion trees of depth meeting the expectation, can be found in time        O    (      m          2      +      ln      ⁡      k        ). Likewise, we discuss analogous results for computing optimal station schedules of TDMA networks.}
}