Date: Tue, 24 Sep 1996 17:53:27 +0900 (JST) From: Michael Hancock <michaelh@cet.co.jp> To: "Hr.Ladavac" <lada@ws2301.gud.siemens.co.at> Cc: fs@FreeBSD.ORG Subject: Re: Transitive Closure--a Question for Terry Message-ID: <Pine.SV4.3.93.960924174530.21455B-100000@parkplace.cet.co.jp> In-Reply-To: <199609101109.AA067513751@ws2301.gud.siemens.co.at>
next in thread | previous in thread | raw e-mail | index | archive | help
It summarizes information in a directed graph. There's a description in "Algorithms in C" by Robert Sedgewick. The book is also a good reference if you want to look at radix tries which are used in couple places in 4.4BSD. Regards, Mike Hancock On Tue, 10 Sep 1996, Hr.Ladavac wrote: > Hi all, especially Terry. > > The term "Transitive Closure" and its calculation has been > repeatedly mentioned in this forum (list, whatever.) > > My personal question is what does it mean to you. To be > honest, I've never stumbled upon the term before, and the > fact that the graph theory textbooks I read were in Russian > is probably no help either. > > My gut tells me it has to do with cycle detection/prevention > in a directed graph, but I cannot be sure. > > If so, the obvious algorithms to use are very simple, albeit > not deterministic in time, with the worst case of O(N**2) > IIRC. > > /Marino >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.SV4.3.93.960924174530.21455B-100000>