Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
type: Item
instance of: scholarly article
title: Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
zbMATH Open document ID: 1370.68234
DOI: 10.1145/3055399.3055447
author: Danupon Nanongkai
author: Thatchaphol Saranurak
publication date: 2017-08-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/1611.03745
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6761883
zbMATH Keywords: dynamic spanning forest
zbMATH Keywords: graph decomposition
zbMATH Keywords: local graph partitioning
zbMATH Keywords: sparse recovery
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2571471359
arXiv ID: 1611.03745
published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
description: scientific article; zbMATH DE number 6761883