Back to Search
Start Over
Faster Fully-Dynamic Minimum Spanning Forest
- Publication Year :
- 2014
-
Abstract
- We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in $O(\log^4n/\log\log n)$ amortized time per operation, improving the $O(\log^4n)$ amortized bound of Holm et al. (STOC'98, JACM'01). We assume the Word-RAM model with standard instructions.<br />Comment: 13 pages, 2 figures
- Subjects :
- Computer Science - Data Structures and Algorithms
E.1
G.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1407.6832
- Document Type :
- Working Paper