Using a small number of sampling views during a CT (computed tomography) exam is a widely accepted technique for low-dose CT reconstruction, which reduces the risk of inducing cancer or other diseases in patients. In this scenario, total variation (TV) based compressed sensing (CS) methods, which uses a regularization term that penalizes the ell-1 norm of the reconstructed image's gradient, outperform the traditional FBP (filtered back-projection) based algorithms in CT reconstruction. Furthermore, in order to reduce well-known artifacts (smoothed edges and texture details) favored by TV-based CS methods, several variants have been proposed, which, in a general context, can be understood as using a regularization term that approximates the ell-0 norm of the reconstructed image's gradient. These type of methods yield state-of-the-art reconstruction results. In this paper we exploit a variant of the ell-0 gradient minimization problem, which directly penalizes the number of non-zero gradients in the reconstructed image, and propose to solve the low-dose CT reconstruction problem. Extended experiments, based on the ASTRA toolbox, show that the propose method is faster (almost twice as fast) and delivers higher quality reconstructions than TV-based CS methods and alternatives that reduce smooth artifacts.