Nearest common ancestors: a survey and a new distributed algorithm

No abstract is available for this paper.

• Publication year

  2002

• Venue

  ACM Symposium on Parallelism in Algorithms and Architectures

• Publication date

  2002-08-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/564870.564914
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Dynamic LCA queries on trees

  2005cited by this paper
• Compact routing schemes with low stretch factor

  2003cited by this paper
• Improved labeling scheme for ancestor queries

  2002influential reference
• Compact labeling schemes for ancestor queries

  2001influential reference
• Short and Simple Labels for Small Distances and Other Functions

  2001cited by this paper
• Improved Algorithms for Finding Level Ancestors in Dynamic Trees

  2000cited by this paper
• [서평]「Algorithms on Strings, Trees, and Sequences」

  2000cited by this paper
• The LCA Problem Revisited

  2000influential reference
• Faster deterministic dictionaries

  1999cited by this paper
• Compact routing with minimum stretch

  1999cited by this paper
• Proximity-Preserving Labeling Schemes and Their Applications

  1999cited by this paper
• Computing Vision Points in Polygons

  1999cited by this paper
• Compact routing schemes with low stretch factor (extended abstract)

  1998cited by this paper
• Shortest Paths in Digraphs of Small Treewdith. Part II: Optimal Parallel Algorithms

  1998cited by this paper
• Optimal Suffix Tree Construction with Large Alphabets

  1997cited by this paper
• Optimal suffix tree construction with large alphabets

  1997cited by this paper
• Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology

  1997cited by this paper
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees

  1996cited by this paper
• A randomized linear-time algorithm to find minimum spanning trees

  1995cited by this paper
• Finding the k shortest paths

  1994cited by this paper
• Recursive Star-Tree Parallel Data Structure

  1993influential reference
• A robust model for finding optimal evolutionary trees

  1993cited by this paper
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

  1992cited by this paper
• Implicit representation of graphs

  1992cited by this paper
• Fast Incremental Planarity Testing

  1992cited by this paper
• Finding Level-Ancestors in Dynamic Trees

  1991cited by this paper
• Selected papers of the 16th international colloquium on Automata, languages, and programming

  1991cited by this paper
• Data structures for weighted matching and nearest common ancestors with linking

  1990cited by this paper
• Space-Efficient Message Routing in c-Decomposable Networks

  1990cited by this paper
• On Finding Lowest Common Ancestors: Simplification and Parallelization

  1988influential reference
• Separator-based strategies for efficient message routing

  1986cited by this paper
• Scaling and related techniques for geometry problems

  1984influential reference
• Linear verification for spanning trees

  1984cited by this paper
• Fast Algorithms for Finding Nearest Common Ancestors

  1984influential reference
• Storing a sparse table with O(1) worst case access time

  1982cited by this paper
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions

  1981cited by this paper
• A unifying look at data structures

  1980cited by this paper
• A Best Possible Bound for the Weighted Path Length of Binary Search Trees

  1977influential reference
• A space efficient method for the lowest common ancestor problem and an application to finding negative cycles

  1977cited by this paper
• On finding lowest common ancestors in trees

  1973cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper
• Variable-length binary encodings

  1959influential reference

• Consensus based High Consistency Ledger Pruning for DAG-based IoT Blockchain

  2025cites this paper
• Near-Optimal Resilient Labeling Schemes

  2024cites this paper
• Almost Linear Time Algorithms for Some Problems on Dynamic Flow Networks

  2021cites this paper
• Almost Linear Time Algorithms for Minsum k-Sink Problems on Dynamic Flow Path Networks

  2020cites this paper
• Shorter Labels for Routing in Trees

  2020cites this paper
• Interval Query Problem on Cube-free Median Graphs

  2020cites this paper
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

  2020influential citation
• Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees

  2017cites this paper
• Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes

  2017influential citation
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

  2016cites this paper
• An Optimal Ancestry Labeling Scheme with Applications to XML Trees and Universal Posets

  2016cites this paper
• Algorithms to Compute the Lyndon Array

  2016influential citation
• Adaptive constraint solving for information flow analysis

  2015cites this paper
• Capacity-Constrained Network-Voronoi Diagram

  2015cites this paper
• Randomized proof-labeling schemes

  2015cites this paper
• Properties of the Lowest Common Ancestor in a Complete Binary Tree

  2015cites this paper
• Spatial Network Big Data: Challenges, Approaches, and Opportunities

  2015cites this paper
• Parent Queries over Dynamic Balanced Parenthesis Strings

  2014influential citation
• A Simple and Optimal Ancestry Labeling Scheme for Trees

  2014cites this paper
• Labeling Schemes for Bounded Degree Graphs

  2014cites this paper
• Energy efficient clearance routing in WSN

  2014cites this paper
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs

  2013cites this paper
• Kernel Based Mechanisms for High Performance I/O

  2013cites this paper
• Some Graph Algorithms And Related Primitives For The GPU

  2012influential citation
• Connectivity Oracles for Planar Graphs

  2012cites this paper
• Hop-based approach for holes and boundary detection in wireless sensor networks

  2012cites this paper
• Running Max/Min Filters Using 1+o(1) Comparisons per Sample

  2011cites this paper
• Nearest keyword search in XML documents

  2011influential citation
• Some Graph Algorithms And Related Primitives For The GPU

  2011cites this paper
• Resilient and Low Stretch Routing through Embedding into Tree Metrics

  2011cites this paper
• Data structures for range minimum queries in multidimensional arrays

  2010cites this paper
• Compact ancestry labeling schemes for XML trees

  2010cites this paper
• Finding Range Minima in the Middle: Approximations and Applications

  2010cites this paper
• Efficient Discrete Range Searching primitives on the GPU with applications

  2010cites this paper
• An optimal ancestry scheme and small universal posets

  2010cites this paper
• Parsing Algorithms for Data Compression

  2010influential citation
• On Space Efficient Two Dimensional Range Minimum Data Structures

  2010cites this paper
• Hardware Acceleration of Approximate Tandem Repeat Detection

  2010cites this paper
• An Optimal Labeling for Node Connectivity

  2009cites this paper
• Geometry Discovery with Connectivity Information and Applications in Sensor Networks

  2009influential citation
• A note on models for graph representations

  2009influential citation
• Compact Ancestry Labeling Schemes for Trees of Small Depth

  2009cites this paper
• Faster entropy-bounded compressed suffix trees

  2009cites this paper
• An Optimal Labeling Scheme for Ancestry Queries

  2009cites this paper
• Informative Labeling Schemes for the Least Common Ancestor Problem

  2009cites this paper
• Lecture notes for “ Advanced Graph Algorithms ” : Verification of Minimum Spanning Trees

  2009cites this paper
• Algorithms incorporating concurrency and caching

  2009cites this paper
• Range Minimum Queries : Simple and Optimal , At Last !

  2008cites this paper
• Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors

  2008cites this paper
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems

  2008cites this paper
• A Survey of Boundary Detection Algorithms for Sensor Networks

  2008cites this paper
• Practical Entropy-Bounded Schemes for O(1)-Range Minimum Queries

  2008influential citation
• Hardware acceleration of approximate palindromes searching

  2008cites this paper
• Modifications of the Landau-Vishkin Algorithm Computing Longest Common Extensions via Suffix Arrays and Efficient RMQ computations

  2008cites this paper
• Optimal Succinctness for Range Minimum Queries

  2008influential citation
• The saga of minimum spanning trees

  2008cites this paper
• Suffix Arrays on Words

  2007cites this paper
• Fast computation of small cuts via cycle space sampling

  2007cites this paper
• Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs

  2007cites this paper
• On coding labeled trees

  2007cites this paper
• Efficient Evaluation of Nearest Common Ancestor in XML Twig Queries Using Tree-Unaware RDBMS

  2007cites this paper
• CEPAGE Chercher et Essaimer dans les Plates-formes A Grande Echelle Proposition de Projet – UR Futurs (Bordeaux)

  2007cites this paper
• Data Structures for Efficient String Algorithms

  2007influential citation
• Controller and estimator for dynamic networks

  2007cites this paper
• Simple Linear Work SuÆx Array Constru tion ?

  2007cites this paper
• Compact Forbidden-Set Routing

  2007cites this paper
• Compact Labeling Scheme for XML Ancestor Queries

  2007cites this paper
• Compact separator decompositions in dynamic trees and applications to labeling schemes

  2007influential citation
• Adaptive algorithms for weighted queries on weighted binary relations and labeled trees

  2007cites this paper
• Labeling schemes for vertex connectivity

  2007cites this paper
• Forbidden-Set Labeling on Graphs

  2007cites this paper
• Forbidden-Set Labeling on Graphs B

  2007cites this paper
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array

  2007influential citation
• XML schema matching : balancing efficiency and effectiveness by means of clustering

  2006influential citation
• Boundary recognition in sensor networks by topological methods

  2006influential citation
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

  2006cites this paper
• Labeling Schemes with Queries

  2006cites this paper
• Constructing Labeling Schemes through Universal Matrices

  2006cites this paper
• TWIX: twig structure and content matching of selective queries using binary labeling

  2006cites this paper
• A Dynamic Implicit Adjacency Labelling Scheme for Line Graphs

  2005cites this paper
• Average case analysis for tree labelling schemes

  2005influential citation
• Provably Good Race Detection That Runs in Parallel

  2005cites this paper
• General compact labeling schemes for dynamic trees

  2005influential citation
• TWIX : Approximate and Exact Twig Structure and Content Matching over XML Document Collections using Binary Labeling

  2005influential citation
• JavaSplitter. A Java Implementation of Variable Splitting Proof Search

  2005cites this paper
• Finding Optimal Pairs of Patterns

  2004cites this paper
• Distributed Computation for Swapping a Failing Edge

  2004cites this paper
• On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

  2004cites this paper
• An O(N/sup 2/) algorithm for discovering optimal Boolean pattern pairs

  2004cites this paper
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time

  2004cites this paper
• Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance

  2004cites this paper
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

  2004cites this paper
• Vertex disjoint paths on clique-width bounded graphs

  2004cites this paper
• The Least Common Ancestor Problem

  2003cites this paper
• Compact and localized distributed data structures

  2003cites this paper
• Simple Linear Work Suffix Array Construction

  2003cites this paper
• Äóöøóóö Óöððð× Ê Blockin Blockin Blockinö Ò Áòòóöññøøõùù Íåê ¼¼ ¹ Íòòúö××ø Óööööùü Á¸¿¿½¸óùö× Ðð Äää Ööøøóò¸¿¿¿¼¼ Ìððò ܸööò

  2003cites this paper
• Labeling schemes for small distances in trees

  2003cites this paper
• Space-eecient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting

  2003cites this paper
• Distance labeling scheme and split decomposition

  2003cites this paper