An Efficient Method for Storing Ancestor Information in Trees
Author:
- David MaierDMDavid Maier
- 1 November 1979
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 8 (4) , 599-618
Abstract
We present a space efficient method for computing ancestor information in trees, specifically, whether one node is an ancestor of another and the lowest common ancestor of two nodes. We show the method is tunable to specific applications, and compare it to other methods. Finally, we apply our procedures to the problem of finding negative cycles in sparse graphs.Keywords
This publication has 11 references indexed in Scilit:
- Efficient Algorithms for Shortest Paths in Sparse NetworksJournal of the ACM, 1977
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- On Finding Lowest Common Ancestors in TreesSIAM Journal on Computing, 1976
- Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)Networks, 1975
- Technical Contributions Finding Negative Cycles*INFOR: Information Systems and Operational Research, 1973
- Notes—On the Efficiency of a Direct Search Method to Locate Negative Cycles in a NetworkManagement Science, 1972
- A Direct Search Method to Locate Negative Cycles in a GraphManagement Science, 1971
- An algorithm for finding shortest routes from all source nodes to a given destination in general networksQuarterly of Applied Mathematics, 1970
- An Appraisal of Some Shortest-Path AlgorithmsOperations Research, 1969
- A Decomposition Algorithm for Shortest Paths in a NetworkOperations Research, 1968