Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, Julian Shun
Abstract
Maintaining a k-core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that a single update to the graph can cause significant global changes. Our paper focuses on approximation algorithms with small approximation factors that are much more efficient than what exact algorithms can obtain.
Topics & Concepts
Computer scienceDecompositionGraphAlgorithmCore (optical fiber)Approximation algorithmGraph algorithmsPower graph analysisTheoretical computer scienceBiologyTelecommunicationsEcologyComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchGraph Theory and Algorithms