Posts classified under: General

Enumerating is the task of generating all solutions associated with an instance of a computational problem. We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In … Continue reading Séminaire Algorithmique : « Enumeration Classes Defined by Circuits », Arnaud Durand (IMJ, Univ. Paris-Diderot)

Balanced binary search trees are a common data structure for implementing ordered sets, with three kinds of queries: checking whether a given value belongs to the set, inserting a value, and deleting a value; the two latter queries require updating the data structure. Some implementations, like red-black trees or weak AVL trees, allow efficient update … Continue reading Séminaire algorithmique : Vincent Jugé (LIGM, Univ. G. Eiffel, Paris Est), « Write-efficient updates for AVL trees »