On Finding Lowest Common Ancestors: Simplification and Parallelization
From MaRDI portal
Publication:3823152
DOI10.1137/0217079zbMath0669.68049OpenAlexW2046946959WikidataQ56563676 ScholiaQ56563676MaRDI QIDQ3823152
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
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)
Related Items (only showing first 100 items - show all)
Efficient parallel modular decomposition (extended abstract) ⋮ Graph ear decompositions and graph embeddings ⋮ Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint ⋮ THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW ⋮ Optimal parallel suffix tree construction ⋮ Euler is standing in line dial-a-ride problems with precedence-constraints ⋮ Minimal absent words in rooted and unrooted trees ⋮ Suffix arrays for multiple strings: a method for on-line multiple string searches ⋮ ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES ⋮ Sequential and parallel algorithms for the NCA problem on pure pointer machines ⋮ New algorithms for the LCA problem and the binary tree reconstruction problem ⋮ Finding level-ancestors in trees ⋮ Finding lowest common ancestors in arbitrarily directed trees ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Cache Oblivious Minimum Cut ⋮ Sublinear approximate string matching and biological applications ⋮ Pattern matching in a digitized image ⋮ When can you fold a map? ⋮ Common intervals of trees ⋮ Online timestamped text indexing ⋮ Planarity testing in parallel ⋮ Approximating points by a piecewise linear function ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs ⋮ Faster enumeration of all spanning trees of a directed graph ⋮ Rectilinear short path queries among rectangular obstacles ⋮ A note on finding compact sets in graphs represented by an adjacency list ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ A simpler minimum spanning tree verification algorithm ⋮ On the range maximum-sum segment query problem ⋮ Computing longest common extensions in partial words ⋮ Simple Parallel Algorithms for Dynamic Range Products ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ Unified all-pairs shortest path algorithms in the chordal hierarchy ⋮ Compact separator decompositions in dynamic trees and applications to labeling schemes ⋮ Designing checkers for programs that run in parallel ⋮ The suffix tree of a tree and minimizing sequential transducers ⋮ Data-Oblivious Graph Algorithms in Outsourced External Memory ⋮ Drawing \(c\)-planar biconnected clustered graphs ⋮ On the Galois Lattice of Bipartite Distance Hereditary Graphs ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ Satisfiability problems on intervals and unit intervals ⋮ Variations of the parameterized longest previous factor ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Checking whether a word is Hamming-isometric in linear time ⋮ Best match graphs ⋮ Optimal parallel colouring algorithms for totally decomposable graphs ⋮ Cache oblivious algorithms for the RMQ and the RMSQ problems ⋮ Linear-time construction of two-dimensional suffix trees ⋮ A Path Cover Technique for LCAs in Dags ⋮ Improved algorithms for the range next value problem and applications ⋮ Efficient algorithms for local ranking ⋮ The longest common substring problem ⋮ Recognizing breadth-first search trees in linear time ⋮ Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication ⋮ Parallel algorithms for the segment dragging problem ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ The lowest common ancestor problem on a tree with an unfixed root ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Searching for a set of correlated patterns ⋮ Kinetic collision detection between two simple polygons. ⋮ Compact and localized distributed data structures ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Algorithms for extracting motifs from biological weighted sequences ⋮ Linear time algorithm for the longest common repeat problem ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ Efficient algorithms for shortest distance queries on special classes of polygons ⋮ Fast average-case pattern matching by multiplexing sparse tables ⋮ The weighted maximum independent set problem in permutation graphs ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ On Cartesian trees and range minimum queries ⋮ On space efficient two dimensional range minimum data structures ⋮ A parallel algorithm for approximating the minimum cycle cover ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Testing convexity properties of tree colorings ⋮ Spaces, Trees, and Colors ⋮ Faster query algorithms for the text fingerprinting problem ⋮ Single backup table schemes for shortest-path routing ⋮ On the restricted 1-Steiner tree problem ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ A simpler minimum spanning tree verification algorithm ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ Longest repeats with a block of \(k\) don't cares ⋮ Succinct Greedy Graph Drawing in the Hyperbolic Plane ⋮ FINDING ALL APPROXIMATE GAPPED PALINDROMES ⋮ Efficient pattern matching in elastic-degenerate strings ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Reciprocal best match graphs ⋮ Real two dimensional scaled matching ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms ⋮ Discovering subword associations in strings in time linear in the output size ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Range minimum queries in minimal space ⋮ Two flow network simplification algorithms
This page was built for publication: On Finding Lowest Common Ancestors: Simplification and Parallelization
