4 ms·
What is meant by "nodes" in this article? > sum of the number of nodes and connections > Bellman-Ford instead needs many more steps: The total is based on the
by cvoss 3y ago
What is meant by "nodes" in this article?
> sum of the number of nodes and connections
> Bellman-Ford instead needs many more steps: The total is based on the product of the number of nodes and vertices.
> reduced the complexity to the square root of the number of vertices multiplied by the number of nodes
At first I thought it was a synonym for vertices, in the same way the article inconsistently uses "connections" for edges. But then "nodes" gets used in the same breath as "vertices" in a way that contradicts that hypothesis.
- brutusborn 3y agoI only had a quick skim but the first paper describes a graph transformation to remove cycles. So I think that nodes are essentially a subgraph of vertices that contain cycles.
- dataflow 3y agoLooks 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