Absolute pose estimation from corrupted point correspondences is typically a problem of estimating parameters from outlier-contaminated data. Conventionally, for a fixed dimensionality d and the number of measurements N, a robust estimation problem cannot be solved exactly faster than O ( N d ) . Furthermore, it is almost impossible to remove d from the exponent of the runtime of a globally optimal algorithm. However, absolute pose estimation is a geometric parameter estimation problem, and thus has special constraints. In this paper, we consider pairwise constraints and propose a novel algorithm utilizing global optimization method Branch-and-Bound (BnB) for solving the absolute pose estimation problem. Concretely, we first decouple the rotation and the translation subproblems by utilizing the pairwise constraints, and then we solve the rotation subproblem using the BnB algorithm. Lastly, we estimate the translation based on the optimal rotation by using another BnB algorithm. The proposed algorithm has an approximately linear complexity in the number of correspondences at a given outlier ratio. The advantages of our method were demonstrated via thorough testing on both synthetic and real-world data.