The covariant phase technique is used to compute the constraint algebra of the four-dimensional space-times which are asymptotic to anti-de Sitter (AdS), such as the planar Taub-NUT AdS and Taub-bolt AdS spaces, and the hyperbolic Taub-bolt AdS space. The standard Virasoro subalgebrae with corresponding central charges for these objects are constructed and the resulting densities of states yield the expected Bekenstein-Hawking entropies.