We present a decomposition procedure that accelerates the computational performance of the tree enumeration method presented by Gala and Bagajewicz [Gala, M.; Bagajewicz, M. Ind. Eng. Chem. Res. 2006, 66796686], which is based on the union of cutsets. The new algorithm, which is rigorous, uses union and a ring sum of cutsets and is based on the decomposition of the graph into subgraphs. The robustness and the efficiency of the proposed algorithm are tested on a large scale refinery problem.