Let $A(x)=(A_{ij}(x))$ be a square matrix with $A_{ij}$ being a polynomial in $x$. This paper proposes "combinatorial relaxation" type algorithms for computing the degree of the determinant, $\delta(A) = \deg_x \det A(x)$, based on its combinatorial upper bound $\widehat \delta(A)$, which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix $A$ and nonbipartite for a skew-symmetric $A$. The algorithm transforms $A$ to another matrix $A'$ for which $\delta(A) = \delta(A') = \widehat \delta(A')$ with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings; it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur.
