This paper presents 3-D brain tissue classification schemes using three recent promising energy minimization methods for Markov random fields: graph cuts, loopy belief propagation and tree-reweighted message passing. The classification is performed using the well known finite Gaussian mixture Markov Random Field model. Results from the above methods are compared with widely used iterative conditional modes algorithm. The evaluation is performed on a dataset containing simulated T1-weighted MR brain volumes with varying noise and intensity non-uniformities. The comparisons are performed in terms of energies as well as based on ground truth segmentations, using various quantitative metrics.