| Errata: | - Word "syntactic":
- All appearances (on pp. 2 and 6, and twice
on p. 9) of this word must be replaced with "synthetic". [Authors’
version corrected, 20 February 2014]
- § 3.2, Description of delete-min:
- The minimum can be in
some of the marked nodes. When the nodes on the path from the deleted
node to the root are sifted one level down, the deleted node is
replaced by another node and not much is known about its relation to
the nodes in the right subtree of the deleted node. [Reported by Dan
Larkin, 10 August 2012]
To correct this error the replacement node should be embedded into the
right subtree by sifting it down. In the actual implementation a
replacement node for the deleted node is borrowed and sifted down as
required. The sifting up is avoided by marking the new root that
replaces the deleted node. This difference between the text (top-down
approach) and the code (bottom-up approach) was not mentioned. - § 5.1, Graph generation:
- In the generated
graph the edges adjacent to vertex vi where those adjacent to
vertex vi+1. [Reported by Lasse Petersen, 14 May 2012]
This error is corrected in the revised version of the source code. For
random graphs this change did not have a significant effect on the
reported running times. - § 5.1, Graph generation:
- The random-graph generator of LEDA
generates multi-graphs, not graphs. [Reported by Lasse Petersen, 14 May 2012]
- § 5.1, Graph traversal:
- The macro
for_each_adjacent_edge visited the first edge twice.
[Reported by Lasse Petersen, 14 May 2012]
This error is corrected in the revised version of the source code. The
effect of this off-by-one error was about the same for all
implementations. Also, the reported running times remained almost the
same.
|
HTML (Conference paper)