D-SLAM algorithm flrst described in (1) allows SLAM to be decou- pled into solving a non-linear static estimation problem for mapping and a three- dimensional estimation problem for localization. This paper presents a new version of the D-SLAM algorithm that uses an absolute map instead of a relative map as presented in (1). One of the signiflcant advantages of D-SLAM algorithm is its O(N) computational cost where N is the total number of features (landmarks). The theo- retical foundations of D-SLAM together with implementation issues including data association, state recovery, and computational complexity are addressed in detail. Evaluation of the D-SLAM algorithm is provided using both real experimental data and simulations.