Re: [boost] another approach to memory management that solves thereferential cycles problem

Subject: Re: [boost] another approach to memory management that solves thereferential cycles problem
From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2009-02-27 15:16:23

> This reminds me of the "Dynamic graph algorithms" To-Do item from the Boost Graph Library:
> 
> http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/challenge.html
> 
> The task at hand seems to be related to the "Dynamic Connectivity" problem. The given references seem to be from 1998 and 1999, but skimming over them gives hope that the problem is not as unsolvable as it seems at first glance: "The currently best theoretic bounds are achieved by a data structure invented by Henzinger and King [13] and improced by Henzinger and Thorup [14]. It achieves O(log n) worst-case deterministic query time and O(log^2 n) amortized expected update time ..."
> 
> I haven't yet looked at your other proposed solutions, but perhaps I will do this later.
> 

Thank you, I will check this out later.