Preserving order in a forest in less than logarithmic time and linear space
From MaRDI portal
Publication:1241058
DOI10.1016/0020-0190(77)90031-XzbMath0364.68053OpenAlexW2152506638MaRDI QIDQ1241058
Publication date: 1977
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(77)90031-x
Related Items
On Locality-Sensitive Orderings and Their Applications, Predecessor queries in dynamic integer sets, Sorting and searching revisted, Query optimization using rewrite rules, Finding the k smallest spanning trees, Two- and three- dimensional point location in rectangular subdivisions, Deferred-query—An efficient approach for problems on interval and circular-arc graphs, Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract), An algorithm for finding predecessors in integer sets, Processing an Offline Insertion-Query Sequence with Applications, Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs, Space Efficient Multi-dimensional Range Reporting, Non-crossing shortest paths lengths in planar graphs in linear time, Absent Subsequences in Words, Non-crossing shortest paths lengths in planar graphs in linear time, Data structures for computing unique palindromes in static and non-static strings, Incremental hive graph, Lower bound framework for differentially private and oblivious data structures, Dominance in the presence of obstacles, Compact and localized distributed data structures, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Trapezoid graphs and generalizations, geometry and algorithms, An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model, Longest increasing subsequence under persistent comparison errors, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Unnamed Item, Unnamed Item, Rollercoasters: Long Sequences without Short Runs, Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs, Fast algorithms for the dominating set problem on permutation graphs, Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings, Dynamic coresets, Enumerating longest increasing subsequences and patience sorting, The property suffix tree with dynamic properties, Longest increasing subsequences in windows based on canonical antichain partition, Rotation and lighting invariant template matching, PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS, Fast and compact regular expression matching, Speeding up transposition-invariant string matching, The longest common subsequence problem revisited, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Finding a maximum matching in a permutation graph, Improved parallel integer sorting without concurrent writing, Finding maximum cliques on circular-arc graphs, Scanline algorithms on a grid, Towards an Optimal Method for Dynamic Planar Point Location, Finding shortest path in the presence of barriers: an alternate approach, Efficient testing and matching of deterministic regular expressions, Shortest unique palindromic substring queries in semi-dynamic settings, An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs, A review of metrics on permutations for search landscape analysis, Efficient algorithms for the minimum connected domination on trapezoid graphs, The net adding problem, Algorithms for interval structures with applications, Fast Dynamic Weight Matchings in Convex Bipartite Graphs, The space-optimal version of a known rectangle enclosure reporting algorithm, A general label search to investigate classical graph search algorithms, Fast Algorithms for Computing Tree LCS, Formally proving size optimality of sorting networks, Unnamed Item, Fast algorithms for computing the constrained LCS of run-length encoded strings, The longest commonly positioned increasing subsequences problem, MOUNTAIN REDUCTION, BLOCK MATCHING, AND APPLICATIONS IN INTENSITY-MODULATED RADIATION THERAPY, Positional Dominance: Concepts and Algorithms, The cost of cache-oblivious searching, A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle, Order-preserving matching, Bounded ordered dictionaries in O(log log N) time and O(n) space, An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals, Fast computation of a longest increasing subsequence and application, The saga of minimum spanning trees, An \(A^\ast\) search algorithm for the constrained longest common subsequence problem, Algorithms for computing variants of the longest common subsequence problem, Using persistent data structures for adding range restrictions to searching problems, Algorithms for extracting motifs from biological weighted sequences, Rollercoasters and Caterpillars, \(k\)-abelian pattern matching, On the generalized constrained longest common subsequence problems, On the longest upsequence problem for permutations, New clique and independent set algorithms for circle graphs, On Locality-Sensitive Orderings and Their Applications, A simple linear-space data structure for constant-time range minimum query, Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem, Dynamic programming with convexity, concavity and sparsity, Trapezoid graphs and generalizations, geometry and algorithms, Improvised divide and conquer approach for the LIS problem, Finding the \(k\) smallest spanning trees, Substring range reporting, More efficient bottom-up multi-pattern matching in trees, Lower bounds for predecessor searching in the cell probe model, Adaptive sampling for geometric problems over data streams, An efficient one-side height minimization algorithm for routing around a rectangle, Dynamic relative compression, dynamic partial sums, and substring concatenation, Range-restricted mergeable priority queues, Finding the gapped longest common subsequence by incremental suffix maximum queries, Efficient algorithms for the longest common subsequence in \(k\)-length substrings, Fast local searches and updates in bounded universes, Linear-space data structures for range mode query in arrays, Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs, Cache-oblivious index for approximate string matching, Finding longest increasing and common subsequences in streaming data, A probabilistic minimum spanning tree algorithm, Biased predecessor search, The power and limitations of static binary search trees with lazy finger, Fast algorithms for computing tree LCS, Dynamic interpolation search revisited, Minimal indices for predecessor search, A new efficient algorithm for computing the longest common subsequence, Space-time trade off in implementing certain set operations, Orthogonal range searching in linear and almost-linear space, A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES, A diagonal-based algorithm for the longest common increasing subsequence problem, Log-logarithmic worst-case range queries are possible in space theta(N), A Survey on Priority Queues, Orthogonal Range Searching for Text Indexing, Chaining algorithms for multiple genome comparison, Upper bounds for sorting integers on random access machines, An O(m log log D) algorithm for shortest paths, A priority queue in which initialization and queue operations takeO(loglogD) time, New trie data structures which support very fast search operations, Optimal Partition of a Bipartite Graph with Prescribed Layout into Non-Crossing b-Matchings, Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs, An efficient algorithm for enumeration of triangulations, Efficient labelling algorithms for the maximum noncrossing matching problem, Data structures on event graphs, A new algorithm for rectangle enclosure reporting, Optimal bounds for the predecessor problem and related problems, Linear-space data structures for range frequency queries on arrays and trees, An axiomatic approach to time-dependent shortest path oracles
Cites Work
