A Note on Two Problems in Connexion with Graphs
Numerische Mathematik, 1959 · paper · Computer science
Gives methods for two graph problems: building the minimum-length tree connecting all nodes, and finding the shortest path between two nodes. The author argues the methods need less simultaneous data storage than earlier solutions.
Checked: PDF from ir.cwi.nl, fetched 4 Oct 2026. Page numbers are those of that PDF.
0 findings
None that passed a second check.
2 minor (typos and the like; most checked by the judge only)
Wording Problem 1 defines B as nodes to each of which "one and only one branch of set II will lead", but the initialisation ("placing all branches that end in this node in set II") and Step 2 ("the corresponding branch in set II") leave B-nodes with no set-II branch when, as the introduction allows, only "some" pairs of nodes are connected.
- p. 1 Problem 1, definition of node set B
one and only one branch of set II will lead to each of these nodes
- p. 1 Problem 1, initialisation
by placing all branches that end in this node in set II
- p. 1 Problem 1, Step 2
If the branch under consideration is longer than the corresponding branch in set II, it is rejected
- p. 1 Problem 1, definition of node set B
B. the remaining nodes (one and only one branch of set II will lead to each of these nodes).
Only the authors can say what is right here.
Judge's note: Checked page 1 image (main-p001.png). The introduction reads "some or all pairs of which are connected by a branch" (the text layer has OCR "arc" for "are", which is why that quote was not found). B is defined with the parenthetical "one and only one branch of set II will lead to each of these nodes". At initialisation only the branches touching the start node go into set II. So in a non-complete graph, any B-node not adjacent to the start node has no set-II branch, and the invariant fails at that point. Step 2 then compares against "the corresponding branch in set II" but gives no rule for when no such branch exists. Problem 2 (page 2) covers this case explicitly with set C ("If the node R belongs to set C, it is added to set B and branch r is added to set II"). The obvious reading (treat a missing branch as infinitely long, or add the branch) is not stated anywhere in the paper. The gap is in the description, not the method, so I rate it as a wording/ambiguity point for the author.
Second check: another model agreed
Report a problem with this finding
Wording Problem 1 Step 2 says "If the branch under consideration is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces the corresponding branch" and so says nothing about branches of equal length.
- p. 1 Problem 1, Step 2
If the branch under con-sideration is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces
Judge's note: Checked Step 2 on the page 1 image. Only the 'longer' and 'shorter' cases are stated. Problem 2 Step 1 (page 2) is worded so that ties are covered: it asks whether the new path is "shorter", and "If this is not so, branch r is rejected". Either way of breaking a tie gives a minimum tree, so the result is not affected. This is only an incompleteness in how the rule is worded, and it is inconsistent with the Problem 2 wording.
Second check: another model agreed