The tradition of looking for linear time algorithms for
non-sparse graphs goes back at least to Fibonacci heaps, which can be used for solving single source shortest paths in \(O(m+n\log n)\)  time [1]}. Our results show that another fundamental graph problem can be solved in linear time in the non-sparse case.
