A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
The LCA Problem Revisited
4 Pith papers cite this work, alongside 5 external citations. Polarity classification is still indexing.
4
Pith papers citing it
5
external citations · Crossref
citation-role summary
method 1
citation-polarity summary
verdicts
UNVERDICTED 4roles
method 1polarities
use method 1representative citing papers
Data structures achieve O(log* n) per operation for tree-sum queries on decremental forests using micro-macro decomposition, plus a universally optimal algorithm in the group model.
New algorithms compute shortest unique and absent substrings in O(n log σ / sqrt(log n)) time by decomposing on length and period then reducing to geometric queries via synchronizing sets, runs, and wavelet trees.
The paper introduces minimal and shortest absent subsequences, gives combinatorial characterizations with compact representations, and provides efficient algorithms to test membership and compute the lexicographically smallest ones along with a query data structure.
citing papers explorer
-
Undirected Replacement Paths: Dual Fault Reduces to Single Source
A weight-preserving reduction from undirected 2-FRP to SSRP establishes their computational equivalence and yields matching improved algorithms for 2-FRP.
-
Fast decremental tree sums in forests
Data structures achieve O(log* n) per operation for tree-sum queries on decremental forests using micro-macro decomposition, plus a universally optimal algorithm in the group model.
-
Faster Algorithms for Shortest Unique or Absent Substrings
New algorithms compute shortest unique and absent substrings in O(n log σ / sqrt(log n)) time by decomposing on length and period then reducing to geometric queries via synchronizing sets, runs, and wavelet trees.
-
Absent Subsequences in Words
The paper introduces minimal and shortest absent subsequences, gives combinatorial characterizations with compact representations, and provides efficient algorithms to test membership and compute the lexicographically smallest ones along with a query data structure.