On Finding Lowest Common Ancestors: Simplification and Parallelization

DOI10.1137/0217079zbMATH Open0669.68049OpenAlexW2046946959WikidataQ56563676 ScholiaQ56563676MaRDI QIDQ3823152FDOQ3823152

Authors: Baruch Schieber, Uzi Vishkin 

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217079

Recommendations

• scientific article; zbMATH DE number 4064469
• Finding Lowest Common Ancestors in Parallel
• A fast cost-optimal parallel algorithm for the lowest common ancestor problem
• Fast Lowest Common Ancestor Computations in Dags
• Finding lowest common ancestors in arbitrarily directed trees
• scientific article; zbMATH DE number 753968
• Parallel dynamic lowest common ancestors
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast smallest lowest common ancestor computation based on stable match

zbMATH Keywords

parallel algorithmsfree algorithmslowest common ancestor problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Cited In (only showing first 100 items - show all)

• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Satisfiability problems on intervals and unit intervals
• Optimal parallel colouring algorithms for totally decomposable graphs
• The weighted maximum independent set problem in permutation graphs
• Recognizing breadth-first search trees in linear time
• When can you fold a map?
• Common intervals of trees
• Testing convexity properties of tree colorings
• A quick tour on suffix arrays and compressed suffix arrays
• Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
• Sublinear approximate string matching and biological applications
• Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint
• Variations of the parameterized longest previous factor
• Rectilinear short path queries among rectangular obstacles
• A fast cost-optimal parallel algorithm for the lowest common ancestor problem
• Graph ear decompositions and graph embeddings
• Linear time algorithm for the longest common repeat problem
• Finding lowest common ancestors in arbitrarily directed trees
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• Approximating points by a piecewise linear function
• On the range maximum-sum segment query problem
• Pattern matching in a digitized image
• Two flow network simplification algorithms
• Improved algorithms for the range next value problem and applications
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Efficient algorithms for local ranking
• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• Online timestamped text indexing
• Geometric biplane graphs. II: Graph augmentation
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• The longest common extension problem revisited and applications to approximate string searching
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
• Euler is standing in line dial-a-ride problems with precedence-constraints
• On space efficient two dimensional range minimum data structures
• Range minimum queries in minimal space
• Ray shooting in polygons using geodesic triangulations
• Faster query algorithms for the text fingerprinting problem
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Reconstructing a history of recombinations from a set of sequences
• Real two dimensional scaled matching
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• The suffix tree of a tree and minimizing sequential transducers
• Fast parallel and serial multidimensional approximate array matching
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A simpler minimum spanning tree verification algorithm
• Finding level-ancestors in trees
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Single backup table schemes for shortest-path routing
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Cache oblivious algorithms for the RMQ and the RMSQ problems
• Linear-time construction of two-dimensional suffix trees
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• A Path Cover Technique for LCAs in Dags
• Drawing \(c\)-planar biconnected clustered graphs
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• Constant delay traversal of grammar-compressed graphs with bounded rank
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• Parallel algorithms for the segment dragging problem
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• Longest repeats with a block of \(k\) don't cares
• Kinetic collision detection between two simple polygons.
• FINDING ALL APPROXIMATE GAPPED PALINDROMES
• Dynamic algorithms for graphs of bounded treewidth
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• The longest common substring problem
• Sequential and parallel algorithms for the NCA problem on pure pointer machines
• Title not available (Why is that?)
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• Fast Algorithms for Finding Nearest Common Ancestors
• Efficient algorithms for shortest distance queries on special classes of polygons
• On Cartesian trees and range minimum queries
• Longest substring palindrome after edit
• Parallel preprocessing for path queries without concurrent reading.
• A fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree
• Fast smallest lowest common ancestor computation based on stable match
• Suffix arrays for multiple strings: a method for on-line multiple string searches
• Computing longest common extensions in partial words
• Data-oblivious graph algorithms in outsourced external memory
• Optimal parallel suffix tree construction
• Compact and localized distributed data structures
• Algorithms for extracting motifs from biological weighted sequences
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• Designing checkers for programs that run in parallel
• On the restricted 1-Steiner tree problem
• On the restricted \(k\)-Steiner tree problem
• Cache oblivious minimum cut
• Parallel dynamic lowest common ancestors
• Parallel range minima on coarse grained multicomputers
• Finding Lowest Common Ancestors in Parallel
• Best match graphs
• Computing longest palindromic substring after single-character or block-wise edits
• A simpler minimum spanning tree verification algorithm
• The lowest common ancestor problem on a tree with an unfixed root
• Efficient parallel modular decomposition (extended abstract)
• THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW
• FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
• Discovering subword associations in strings in time linear in the output size
• New algorithms for the LCA problem and the binary tree reconstruction problem

This page was built for publication: On Finding Lowest Common Ancestors: Simplification and Parallelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3823152)