Dynamic Bayesian networks (DBNs) have been receiving increased attention as a tool for modeling complex stochastic processes, especially that they generalize the popular Hidden Markov Models (HMMs) and Kalman ยฎlters. Since DBNs are only a subclass of standard Bayesian networks, the structure-based algorithms developed for Bayesian networks can be immediately applied to reasoning with DBNs. Such structurebased algorithms, which are variations on elimination algorithms, take ON expw time and space to compute the likelihood of an event, where N is the number of nodes in the network and w is the width of a corresponding elimination order. DBNs, however, pose two speciยฎc computational challenges that require DBN-speciยฎc solutions. First, DBNs are typically heavily connected, therefore, admitting only elimination orders of high width. Second, even if one can ยฎnd an elimination order of a reasonable width, one cannot aord the space complexity of ON expw since N nT in this case, where n is the number of variables per time slice and T is the number of time slices in the DBN. For many applications, T is very large, making the space complexity of OnT expw unrealistic. Therefore, one of the key challenges of DBNs is to develop ecient algorithms which space complexity is independent of the time span T, leading to what is known as constant-space algorithms. We study one of the main algorithms for achieving this constant-space complexity in this paper, which is based on ``slice-by-slice'' elimination orders, and then suggest improvements on it based on new classes of elimination orders. We identify two topological parameters for DBNs and use them to prove a number of tight bounds on the time complexity of algorithms that we study. We also observe (experimentally) that the newly identiยฎed elimination orders tend to be better than ones based on general purpose elimination heuristics, such as min-ยฎll. This suggests