In this work, we study several implementations of the variational formulation of classical morphological operators such as erosion, dilation, opening, and closing, as well as arbitrary rank filters using convex optimization over graphs. Since the structuring element can naturally vary along nodes in the graph, this formulation allows for an effective implementation of spatially-variant mathematical morphology. It is particularly efficient on massively parallel architectures. We focus on solving the associated optimization problems using various algorithms from convex analysis. The problem being non-smooth, we consider algorithms based on the proximal operator, such as ADMM and PPXA+. We tested these approaches on both images and graph data. Our results show that proximal algorithms can handle the problems efficiently. We believe that this variational framework is a promising direction to combine mathematical morphology with modern computational tools, and is a direct avenue for solving inverse problems with mathematical morphology operators in the formulation.