Looks like a significant and confusing typographical error to me. In the 2nd and 3rd item I think by "nodes" they actually meant "edges". The paper in question

Looks like a significant and confusing typographical error to me. In the 2nd and 3rd item I think by "nodes" they actually meant "edges". The paper in question in the 3rd item you listed is Scaling algorithms for the shortest paths problem, in which the paper says [1] the complexity is proportional to the square root of the number of "nodes", multiplied by the number of "arcs" (edges). [1] https://epubs.siam.org/doi/epdf/10.1137/S0097539792231179 https://epubs.siam.org/doi/epdf/10.1137/S0097539792231179