From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, MAILING_LIST_MULTI,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 30263 invoked from network); 11 May 2022 12:55:47 -0000 Received: from minnie.tuhs.org (45.79.103.53) by inbox.vuxu.org with ESMTPUTF8; 11 May 2022 12:55:47 -0000 Received: by minnie.tuhs.org (Postfix, from userid 112) id 5674D9BCC3; Wed, 11 May 2022 22:55:45 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 5DC8F9BA54; Wed, 11 May 2022 22:55:01 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=fail reason="signature verification failed" (2048-bit key; secure) header.d=celo.io header.i=@celo.io header.b="GqWCIMpI"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 3DDC39BA54; Wed, 11 May 2022 22:54:59 +1000 (AEST) X-Greylist: delayed 429 seconds by postgrey-1.36 at minnie.tuhs.org; Wed, 11 May 2022 22:54:57 AEST Received: from smtp1.servers.tyktech.dk (smtp1.servers.tyktech.dk [85.209.118.35]) by minnie.tuhs.org (Postfix) with ESMTPS id 4FE4E9BA39 for ; Wed, 11 May 2022 22:54:57 +1000 (AEST) Message-ID: <36b91424-e446-ce38-feff-4e84479f9004@celo.io> DKIM-Filter: OpenDKIM Filter v2.10.3 smtp1.servers.tyktech.dk 3429310F1C DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=celo.io; s=default; t=1652273265; bh=dO53k3L2pdy9/QEtb7RTpr/zMMHOP89+Hi9mF7xHyOo=; h=Date:From:Subject:To:References:In-Reply-To; b=GqWCIMpIqU9jxRpWeyKHm22o1boqAKCzv/gunbCsQB59w+7wOZKjHEc0s1h7TeoWu efBVlngh0qQ7urRo9T1v/7jQsUXNuW4GaJQyaafenW4La4aR+toibq/fKAi2VcOdlg j5OS5LbxRcwIc3GEttjim+IhqB6wKVyVFbphv/Xny/GUwuErmhRKW7+MGfKDifQxPA jdJ4zsosYPzjfqoEvmFxNuK8EAILzyx/8Ovq/WQYaXZFndRuxHzR8d7xpnwNALImVC gzNfCUAnaCTGiMrxH2haoAG292qZla25olMT71NiWT9R18a3npjsb1gIQpnDUMdlGa MtpRH3oh1pmww== Date: Wed, 11 May 2022 14:47:44 +0200 MIME-Version: 1.0 From: Joe To: tuhs@minnie.tuhs.org References: Content-Language: en-US In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [TUHS] {TUHS] Interesting Commentary on Unix from Multicians X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" 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