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

[Joe <joe@celo.io>]

On 4/9/22 13:45, Douglas McIlroy wrote:
>> Single Level Storage is an awesome concept and removes so many ugly
>> hacks from algorithms that otherwise have to process data in files.
> 
> This was Vic Vyssotsky's signature contribution to Multics, though in typical
> Vyssotsky fashion he never sought personal credit for it. Other awesome
> Vyssotsky inventions:
> 
> [..]
> A minimum-spanning-tree algorithm quite different from the well-known methods
> due to his colleagues Bob Prim and Joe Kruskal, again unpublished.
> 

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/chapter4/section3/Exercise23_VyssotskyAlgorithm.java
(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/cs226/2002/lectures/19mst.pdf
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