The paper gives a connectivity oracle under k vertex failures with O(k^6) n-independent update time, O(k) query time, and near-linear space and preprocessing for constant k.
Theoretical Computer Science , volume=
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
Presents first linear-space data structures answering path mode and least frequent element queries in O(sqrt(n/w)) time after O(n sqrt(n w)) preprocessing, improving prior O(log log n sqrt(n/w)) bounds, plus faster alpha-minority and a general path maximum g-value color framework.
citing papers explorer
-
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
The paper gives a connectivity oracle under k vertex failures with O(k^6) n-independent update time, O(k) query time, and near-linear space and preprocessing for constant k.
-
Faster Linear-Space Data Structures for Path Frequency Queries
Presents first linear-space data structures answering path mode and least frequent element queries in O(sqrt(n/w)) time after O(n sqrt(n w)) preprocessing, improving prior O(log log n sqrt(n/w)) bounds, plus faster alpha-minority and a general path maximum g-value color framework.