confirmed by theoretical analysis, which shows that for graphs with n vertices and m edges, MMD has a tight upper bound of on its running time, whereas for AMD a tight bound of holds. Cummings, Fahrbach, and Fatehpuria designed an exact minimum degree algorithm with running time, and showed that no such algorithm can exist that runs in time , for any , assuming the strong exponential time hypothesis. References Numerical linear algebra Matrix theory