This technical note considers the problem of reducing the computational complexity associated with the Sum-of-Squares approach to stability analysis of time-delay systems. Specifically, this technical note considers systems with a large state-space but where delays affect only certain parts of the system. This yields a coefficient matrix of the delayed state with low rank-a common scenario in practice. The technical note uses the general framework of coupled differential-difference equations with delays in feedback channels. This framework includes systems of both the neutral and retarded-type. The approach is based on recent results which introduced a new Lyapunov-Krasovskii structure which was shown to be necessary and sufficient for stability of this class of systems. This technical note shows how exploiting the structure of the new functional can yield dramatic improvements in computational complexity. Numerical examples are given to illustrate this improvement.