On Finding Lowest Common Ancestors: Simplification and Parallelization

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

Cited in

(only showing first 100 items - show all)

Real two dimensional scaled matching
Discovering subword associations in strings in time linear in the output size
Two flow network simplification algorithms
The suffix tree of a tree and minimizing sequential transducers
Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
Fast average-case pattern matching by multiplexing sparse tables
A fast cost-optimal parallel algorithm for the lowest common ancestor problem
The weighted maximum independent set problem in permutation graphs
A parallel algorithm for approximating the minimum cycle cover
Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
Reconstructing a history of recombinations from a set of sequences
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
Sublinear approximate string matching and biological applications
Pattern matching in a digitized image
Planarity testing in parallel
Efficient parallel recognition algorithms of cographs and distance hereditary graphs
Rectilinear short path queries among rectangular obstacles
A note on finding compact sets in graphs represented by an adjacency list
A simpler minimum spanning tree verification algorithm
Unified all-pairs shortest path algorithms in the chordal hierarchy
Satisfiability problems on intervals and unit intervals
Kinetic collision detection between two simple polygons.
Computing longest common extensions in partial words
Single backup table schemes for shortest-path routing
Parallel preprocessing for path queries without concurrent reading.
An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
When can you fold a map?
Optimal parallel algorithms for rectilinear link-distance problems
Designing checkers for programs that run in parallel
Variations of the parameterized longest previous factor
The lowest common ancestor problem on a tree with an unfixed root
On the restricted 1-Steiner tree problem
Range minimum queries in minimal space
On the restricted k-Steiner tree problem
Computing longest palindromic substring after single-character or block-wise edits
Fast parallel and serial multidimensional approximate array matching
Reciprocal best match graphs
Geometric biplane graphs. II: Graph augmentation
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
Approximating points by a piecewise linear function
On the range maximum-sum segment query problem
Best match graphs
Fast smallest lowest common ancestor computation based on stable match
Algorithms for extracting motifs from biological weighted sequences
Linear time algorithm for the longest common repeat problem
Longest repeats with a block of \(k\) don't cares
Checking whether a word is Hamming-isometric in linear time
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
A linear-time algorithm for reconciliation of non-binary gene tree and binary species tree
A fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree
Data-oblivious graph algorithms in outsourced external memory
On the Galois Lattice of Bipartite Distance Hereditary Graphs
Online timestamped text indexing
The longest common substring problem
FINDING ALL APPROXIMATE GAPPED PALINDROMES
Fast Algorithms for Finding Nearest Common Ancestors
Simple parallel algorithms for dynamic range products
A Path Cover Technique for LCAs in Dags
Compact separator decompositions in dynamic trees and applications to labeling schemes
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
Succinct Greedy Graph Drawing in the Hyperbolic Plane
Finding Lowest Common Ancestors in Parallel
scientific article; zbMATH DE number 4064469 (Why is no real title available?)
A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
Improved algorithms for the range next value problem and applications
Optimal parallel colouring algorithms for totally decomposable graphs
Efficient algorithms for local ranking
Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
Dynamic algorithms for graphs of bounded treewidth
scientific article; zbMATH DE number 753968 (Why is no real title available?)
FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
Parallel dynamic lowest common ancestors
Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
Faster enumeration of all spanning trees of a directed graph
A simpler minimum spanning tree verification algorithm
Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
Compact and localized distributed data structures
Longest substring palindrome after edit
Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
Parallel range minima on coarse grained multicomputers
Cache oblivious minimum cut
On Cartesian trees and range minimum queries
Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint
A quick tour on suffix arrays and compressed suffix arrays
Testing convexity properties of tree colorings
ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES
Faster query algorithms for the text fingerprinting problem
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
Efficient parallel modular decomposition (extended abstract)
The longest common extension problem revisited and applications to approximate string searching
Graph ear decompositions and graph embeddings
Cache oblivious algorithms for the RMQ and the RMSQ problems
Linear-time construction of two-dimensional suffix trees
Minimal absent words in rooted and unrooted trees

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)