The heaviest induced ancestors problem: better data structures and applications

DOI10.1007/S00453-022-00955-7MaRDI QIDQ2149106zbMATH OpenOpenAlexFDO

Authors Paniz Abedin, Sahar Hooshmand, Arnab Ganguly, Sharma V. Thankachan

Publication date 28 June 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-022-00955-7

zbMATH Keywords

data structurestring algorithmsorthogonal range queries

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• The heaviest induced ancestors problem revisited
• All-Pairs Ancestor Problems in Weighted Dags
• New common ancestor problems in trees and directed acyclic graphs
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• A Data Structure for Nearest Common Ancestors with Linking
• scientific article; zbMATH DE number 7695994
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• On two restricted ancestors tree problems

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• scientific article; zbMATH DE number 2241899 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Computing longest palindromic substring after single-character or block-wise edits
• Data structures for range median queries
• Dynamic and internal longest common substring
• Fast Algorithms for Finding Nearest Common Ancestors
• Fully-functional succinct trees
• Indexing compressed text
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Longest Lyndon Substring After Edit
• Longest common factor after one edit operation
• Longest common substring made fully dynamic
• Longest substring palindrome after edit
• Minimal unique palindromic substrings after single-character substitution
• On Cartesian trees and range minimum queries
• Orthogonal range searching on the RAM, revisited
• Repetition Detection in a Dynamic String
• Searching for a modified pattern in a changing text
• Sorted range reporting
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• The heaviest induced ancestors problem revisited
• Two-dimensional range successor in optimal time and almost linear space

Cited in

(4)

• The heaviest induced ancestors problem revisited
• Weighted ancestors in suffix trees
• A Data Structure for Nearest Common Ancestors with Linking
• Data structures for computing unique palindromes in static and non-static strings

This page was built for publication: The heaviest induced ancestors problem: better data structures and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149106)