We present a simple, arithmetic-free, efficient scheme to compress trees maintaining the nearest common ancestor (NCA) information. We use this compression scheme to provide an O(n + q lg lg n) solution for solving the NCA problem on Pure Pointer Machines (PPMs) (i.e., pointer machines with no arithmetic capabilities) in both the static and dynamic case, where n is the number of add-leaf/delete operations and q is the number of NCA queries. This solution is optimal.
An Optimal Algorithm for Finding NCA on Pure Pointer Machines / DAL PALU', Alessandro; E., Pontelli; D., Ranjan. - 2368:(2002), pp. 428-438. (Intervento presentato al convegno Algorithm Theory - SWAT tenutosi a Turku, Finland nel July 3-5, 2002) [10.1007/3-540-45471-3_44].
An Optimal Algorithm for Finding NCA on Pure Pointer Machines
DAL PALU', Alessandro;
2002-01-01
Abstract
We present a simple, arithmetic-free, efficient scheme to compress trees maintaining the nearest common ancestor (NCA) information. We use this compression scheme to provide an O(n + q lg lg n) solution for solving the NCA problem on Pure Pointer Machines (PPMs) (i.e., pointer machines with no arithmetic capabilities) in both the static and dynamic case, where n is the number of add-leaf/delete operations and q is the number of NCA queries. This solution is optimal.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
