scientific article; zbMATH DE number 1512678
From MaRDI portal
Publication:4508365
zbMath0959.68133MaRDI QIDQ4508365
Martín Farach-Colton, Michael A. Bender
Publication date: 6 May 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Prefix-Suffix Square Completion, Finding Articulation Points of Large Graphs in Linear Time, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, OntCheck: an ontology-driven static correctness checking tool for component-based models, Approximating points by a piecewise linear function, Faster index for property matching, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing, An improved algorithm for the distance constrainedp-center location problem with mutual communication on tree networks, Space-Efficient Frameworks for Top- k String Retrieval, Succinct 2D dictionary matching, Improved range minimum queries, Efficient Data Structures for the Orthogonal Range Successor Problem, On finding the Adams consensus tree, Longest Common Extensions in Trees, Encodings of Range Maximum-Sum Segment Queries and Applications, New Characterizations of Minimum Spanning Trees and of Saliency Maps Based on Quasi-flat Zones, Viscous-Hyperconnected Attribute Filters: A First Algorithm, Internal shortest absent word queries in constant time and linear space, On Prefix/Suffix-Square Free Words, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Better Process Mapping and Sparse Quadratic Assignment, Absent Subsequences in Words, Maximal degenerate palindromes with gaps and mismatches, Building a small and informative phylogenetic supertree, Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees, Shortest beer path queries in outerplanar graphs, The “Runs” Theorem, A duality based 2-approximation algorithm for maximum agreement forest, Time-Optimal Top-$k$ Document Retrieval, The longest common substring problem, Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings, Computing Longest Single-arm-gapped Palindromes in a String, On the generalized multiway cut in trees problem, Wavelet trees for all, Simple and efficient LZW-compressed multiple pattern matching, A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs, Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane, Building Cartesian trees from free trees with \(k\) leaves, Strong Steiner Tree Approximations in Practice, Linear time algorithm for the longest common repeat problem, Character sets of strings, Efficient Computation of 2-Covers of a String., Algorithms for radius-optimally augmenting trees in a metric space, The Most Likely Object to be Seen Through a Window, Longest Common Factor After One Edit Operation, Shortest-Path Queries in Geometric Networks, Spaces, Trees, and Colors, Forty Years of Text Indexing, Opportunistic data structures for range queries, An improved algorithm for diameter-optimally augmenting paths in a metric space, Unnamed Item, Unnamed Item, Faster algorithms for 1-mappability of a sequence, Compressed indexes for approximate string matching, Fully Functional Static and Dynamic Succinct Trees, A linear-time algorithm for radius-optimally augmenting paths in a metric space, From Gene Trees to Species Trees through a Supertree Approach, Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks, Unnamed Item, A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, Longest common substring made fully dynamic, Unnamed Item, Covering uncertain points in a tree, Connectivity Oracles for Graphs Subject to Vertex Failures, Finding Gapped Palindromes Online, Range LCP, Bootstrapping Algorithms for Gene Duplication and Speciation Events, Computing runs on a trie, Faster queries for longest substring palindrome after block edit, General Document Retrieval in Compact Space, Covering a set of line segments with a few squares, Quickest visibility queries in polygonal domains, Comparing Degenerate Strings, Unnamed Item, Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane, Bicriteria Data Compression, Small-space LCE data structure with constant-time queries, Detecting Locus Acquisition Events in Gene Trees, Array Range Queries, Closest-pair queries in fat rectangles, Constructing suffix arrays in linear time, Quasi-linear algorithms for the topological watershed, Ultrametric fitting by gradient descent *, Average stretch factor: how low does it go?, Efficient Identification of k-Closed Strings, Unnamed Item, Unnamed Item, Geometric biplane graphs. II: Graph augmentation, A note on the longest common substring with \(k\)-mismatches problem, Longest common substrings with \(k\) mismatches, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Fully Dynamic Connectivity Oracles under General Vertex Updates, Computing the \(K\)-terminal reliability of directed path graphs, Disconnectivity and relative positions in simultaneous embeddings, Fast algorithms for approximate Fréchet matching queries in geometric trees, Tree-Based Coarsening and Partitioning of Complex Networks, Linear-Time Algorithm for Long LCF with k Mismatches, Longest substring palindrome after edit, Longest Common Subsequence with Gap Constraints, Geometric hitting set for line-constrained disks, Dynamic convex hulls under window-sliding updates, Elastic-degenerate string matching with 1 error, Faster algorithms for largest empty rectangles and boxes, Sequential and parallel algorithms for the NCA problem on pure pointer machines, Efficiently computing runs on a trie, Extended suffix array construction using Lyndon factors, Algorithms for radius-optimally augmenting trees in a metric space, Approximating geometric bottleneck shortest paths, Longest common extensions in trees, Computing minimal and maximal suffixes of a substring, Order-preserving indexing, Order-preserving pattern matching with \(k\) mismatches, Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps, Computing suffix links for suffix trees and arrays, The heaviest induced ancestors problem: better data structures and applications, Computing longest common extensions in partial words, An improved approximation algorithm for the discrete Fréchet distance, Computing \(k\)-centers of uncertain points on a real line, Simultaneous encodings for range and next/previous larger/smaller value queries, The range 1 query (R1Q) problem, Self-approaching paths in simple polygons, Replacing suffix trees with enhanced suffix arrays, Compressed property suffix trees, One-dimensional approximate point set pattern matching with \(L_p\)-norm, Entropy-bounded representation of point grids, Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, A scalable approach to computing representative lowest common ancestor in directed acyclic graphs, Cross-document pattern matching, Variations of the parameterized longest previous factor, Efficient index for retrieving top-\(k\) most frequent documents, The longest common extension problem revisited and applications to approximate string searching, Improved data structures for the orthogonal range successor problem, On the equivalence between hierarchical segmentations and ultrametric watersheds, An introduction to the Ribe program, Efficient algorithms for three variants of the LPF table, A new efficient indexing algorithm for one-dimensional real scaled patterns, Cache oblivious algorithms for the RMQ and the RMSQ problems, Period recovery of strings over the Hamming and edit distances, Efficient algorithms for shortest partial seeds in words, The indexing for one-dimensional proportionally-scaled strings, Fast algorithms for computing the constrained LCS of run-length encoded strings, Improved algorithms for the range next value problem and applications, Constructing the R* consensus tree of two trees in subcubic time, Crochemore's partitioning on weighted strings and applications, Algorithms and combinatorial properties on shortest unique palindromic substrings, Dynamic and internal longest common substring, The saga of minimum spanning trees, Succinct data structures for flexible text retrieval systems, Multidimensional segment trees can do range updates in poly-logarithmic time, Extending common intervals searching from permutations to sequences, Algorithms for computing variants of the longest common subsequence problem, Computing longest palindromic substring after single-character or block-wise edits, A scalable parallelization of the gene duplication problem, Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights, New heuristics for rooted triplet consistency, On string matching with mismatches, Engineering a combinatorial Laplacian solver: lessons learned, Linear-space data structures for range minority query in arrays, Applying the positional Burrows-Wheeler transform to all-pairs Hamming distance, A simple linear-space data structure for constant-time range minimum query, Improved distance sensitivity oracles with subcubic preprocessing time, Simple and efficient fully-functional succinct trees, A prefix array for parameterized strings, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Outlier respecting points approximation, The 2-radius and 2-radiian problems on trees, \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations, Computing the center of uncertain points on tree networks, Efficient algorithms for the longest common subsequence in \(k\)-length substrings, A practical semi-external memory method for approximate pattern matching, On space efficient two dimensional range minimum data structures, Faster approximate string matching for short patterns, Linear-space data structures for range mode query in arrays, Efficient inclusion for a class of XML types with interleaving and counting, A quick tour on suffix arrays and compressed suffix arrays, Bichromatic 2-center of pairs of points, Fitting a step function to a point set, Faster query algorithms for the text fingerprinting problem, Building species trees from larger parts of phylogenomic databases, Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees, Optimal prefix and suffix queries on texts, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, A new framework for addressing temporal range queries and some preliminary results, New space/time tradeoffs for top-\(k\) document retrieval on sequences, On the restricted 1-Steiner tree problem, \(L_{1}\) shortest path queries in simple polygons, Errata for ``Faster index for property matching, Constant-time tree traversal and subtree equality check for grammar-compressed trees, Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings, Faster algorithms for computing the R* consensus tree, Ramsey partitions and proximity data structures, A new efficient algorithm for computing the longest common subsequence, On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines, Efficient computation of longest single-arm-gapped palindromes in a string, Improved algorithms for the multicut and multiflow problems in rooted trees, Space-efficient fully dynamic DFS in undirected graphs, Efficient indexing algorithms for one-dimensional discretely-scaled strings, Range minimum queries in minimal space, On the restricted \(k\)-Steiner tree problem, The fast algorithm for online \(k\)-server problem on trees, An optimal data structure to handle dynamic environments in non-deterministic computations, Linear-space data structures for range frequency queries on arrays and trees
