In this master thesis several novel DEIM formulations are proposed that enable the construction of non-linearly stable hyper-reduced order models (hROMs) of the incompressible Navier-Stokes equations. The hROMs have the same mass, momentum and energy conservation properties as the previously proposed ROM, but they do not suffer of prohibitively expensive computational scaling when the number of POD modes is increased. The first of the proposed methods is the least-squares discrete empirical interpolation method (LSDEIM), which is based on a constrained minimization. The second method is the Sherman-Morrisson discrete empirical interpolation method (SMDEIM), which applies a rank-one correction to the conventional DEIM to conserve energy. The third method is the decoupled least-squares discrete empirical interpolation method (DLSDEIM), which is a generalization of the LSDEIM that allows increasing the size of the measurement space. All methods result in structure-preserving DEIM formulations that have an equivalent computational scaling as the conventional DEIM, but provide provably stable, structure-preserving hROMs. Furthermore, the use of the principal interval decomposition (PID) in the construction of the reduced and DEIM spaces is considered to beat the Kolmogorov barrier.