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 $\mathcal{N}$ be a scheduled $k$-time slot TDMA network with $n$ stations and $m$ links. We showed that an optimal link schedule for $\mathcal{N}$ can be computed recursively with a recursion tree of logarithmic depth $\mathcal{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 $\mathcal{O}(m^{2+\ln k})$. Likewise, we discuss analogous results for computing optimal station schedules of TDMA networks.

A satisfactory partition is a partition of undirected-graph vertices such that the partition has only two nonempty parts, and every vertex has at least as many adjacent vertices in its part as it has in the other part. Generally, the problem of determining whether a given undirected graph has a satisfactory partition is known to be NP-complete. In this paper, we show that for a given undirected graph with $n$ vertices, a satisfactory partition (if any exists) can be computed recursively with a recursion tree of depth of $\mathcal{O}(\ln n)$ in expectation. Subsequently, we show that a satisfactory partition for those undirected graphs with recursion tree depth meeting the expectation can be computed in time $\mathcal{O}(n^3{2}^{\mathcal{O}(\ln n)})$.