β Scribed by Joseph Gil; Alon Itai
No coin nor oath required. For personal study only.
In a virtual memory system, the address space is partitioned into pages, and the main memory serves as a cache to the disk. In this setting, we address the following problem: Given a tree, find an allocation of its nodes to pages, so-called a packing, which optimizes the cache performance for some access pattern to the tree nodes. We investigate a model for tree access in which a node is accessed only via the path leading to it from the root. Two cost functions are considered: the total number of different pages visited in the search, and the number of page faults incurred. It is shown that both functions can be optimized simultaneously. An efficient dynamic programming algorithm to find an optimal packing is presented. The problem of finding an optimal packing which also uses the minimum number of pages is shown to be NP-complete. However, an efficient approximation algorithm is presented. This algorithm finds a packing that uses the minimum number of pages and requires at most one extra page fault per search. Finally, we study this problem in the context of dynamic trees which allow insertions and deletions.
π SIMILAR VOLUMES
We address the problem of verifying that a tree is connected using probe operations which check mutual connectivity between two (or more) leaves of the tree. We present optimal algorithms for determining minimal probe sets that detect all possible edge and vertex faults in arbitrary trees. Our resul
Let G be a graph and let v be a vertex of G. The open neighbourhood N(v) of v is the set of all vertices adjacent with v in G, while the closed neighbourhood of v is N(v) U {v}. A packing of a graph G is a set of vertices whose closed neighbourhoods are pairwise disjoint. Equivalently, a packing of
We present some results concerning edge-disjoint placement of two or three copies of a tree, as well as a theorem about the packing of three trees into the complete graph K,. ## 1. Terminology We shall use standard graph theory notation. A finite, undirected graph G consists of a vertex set V(G) a
**From the author*of P is for Pearl*comes a heart-warming book about family, friendship and what home can mean.** Stella may only be seventeen, but having read every self-help book she can find means she knows a thing or two about helping people. She sure wasn't expecting to be the one in need