In this paper we provide novel algorithms for computing the minimal Geršgorin set for the localizations of eigenvalues. Two strategies for curve tracing are considered: predictor-corrector and triangular grid approximation. We combine these two strategies with two characterizations (explicit and implicit) of the Minimal Geršgorin set to obtain four new numerical algorithms. We show that these algorithms significantly decrease computational complexity, especially for matrices of large size, and compare them on matrices that arise in practically important eigenvalue problems.