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
Efficient parallel modular decomposition (extended abstract), Graph ear decompositions and graph embeddings, 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, 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, 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, Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint, 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, ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES, 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, On the restricted \(k\)-Steiner tree problem, PARALLEL RANGE MINIMA ON COARSE GRAINED MULTICOMPUTERS, Parallel preprocessing for path queries without concurrent reading., Geometric biplane graphs. II: Graph augmentation, A Linear-Time Algorithm for Reconciliation of Non-binary Gene Tree and Binary Species Tree, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗, Longest substring palindrome after edit
