Terminal-pair reliability (TR) in an asynchronous transfer mode (ATM) virtual path (VP) network corresponds to probabilistic quantification of robustness between two VP terminators, given the VP layout and the failure probabilities of physical links. Existing TR algorithms are shown to be unviable for ATM VP networks owing to either high complexities or failure dependency among VPs. The goal of the paper is to propose efficient algorithms for the computation of TR between two VP terminators by means of variants of path-based and cut-based partition methods which have been effectively used for the computation of TR in traditional networks. The first variant, called the path-based virtual path reliability (PVPR) algorithm, partitions the search space based on a physical path embedding the shortest route of VPs from the source terminator to the destination terminator. The second variant, called the cut-based virtual path reliability (CVPR) algorithm, in lieu, performs the partition on the basis of a physical cutset separating the source from the remaining terminators. In both algorithms, each subproblem is recursively processed by means of partition until the source and destination terminators are contracted or disconnected. Experimental results demonstrate that, compared to one promising TR algorithm (called EBRM), both the PVPR and CVPR algorithms improve the running time by five orders of magnitude. In particular, the CVPR outperforms EBRM more than PVPR does in terms of computation time. The two algorithms and their promising results consequently facilitate the real-time computation of the reliability or robustness of ATM VP networks.