2014/07/07 by Seth Pettie, Pettie, Seth
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.1910
Extended abstract appeared in ISAAC 2005
openalex publication_date 2014/07/07 · arxiv created 2014/07/08 · arxiv updated 2014/07/09 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We present a deterministic algorithm for computing the sensitivity of a minimum spanning tree (MST) or shortest path tree in O(mlogα(m,n)) time, where α is the inverse-Ackermann function. This improves upon a long standing bound of O(mα(m,n)) established by Tarjan. Our algorithms are based on an efficient split-findmin data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity. We also give a reduction from MST sensitivity to the MST problem itself. Together with the randomized linear time MST algorithm of Karger, Klein, and Tarjan, this gives another randomized linear time MST sensitivity algoritm.