Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians

On 4/9/22 13:45, Douglas McIlroy wrote: Interesting, I had not heard about this before, and an internet search turned up: (some copy of "Algorithms in C++", by Robert Sedgewick) https://apprize.best/science/algorithms_2/3.html paragraph 4.3.23: graphs(4) -> mst(3) -> vyssotsky(23) https://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/c… (an implementation of this by Rene Argento?) Algorithms in Java, 3rd edition (2003) R. Sedgewick 20.72: Exercises: [V. Vyssotsky] Develop an implementation of the algorithm discussed in Section 20.2 that builds the MST by adding edges one at a time and deleting the longest edges on the cycle formed (see Exercise 20.34). Use a parent-link representation of a forest of MST subtrees. Hint: Reverse links when traversing paths in trees. I was unable to fetch this slide deck https://web.archive.org/web/20081205054614/https://www.cs.princeton.edu/~rs… which also appears to mention it at least in passing: "Other MST algorithms VYSSOTSKY (1960s) add edges one at a time delete longest on cycle formed" Does anyone know of a more complete source on this topic? It is not mentioned on Wikipedia, these seem like appropriate places to place a reference: https://en.wikipedia.org/wiki/Minimum_spanning_tree https://en.wikipedia.org/wiki/Victor_A._Vyssotsky