8 citations · 24 across the 23 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
Constant-Time Dynamic -Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
Monika Henzinger, Pan Peng
With few exceptions (namely, algorithms for maximal matching, -approximate vertex cover, and certain constant-stretch spanners), all known fully dynamic algorithms in general gr…
cs.DS2019
Testable Properties in General Graphs and Random Order Streaming
Artur Czumaj, Hendrik Fichtenberger, Pan Peng +1
We present a novel framework closely linking the areas of property testing and data streaming algorithms in the setting of general graphs. It has been recently shown (Monemizadeh e…
cs.DS2019
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Pan Peng
Due to the massive size of modern network data, local algorithms that run in sublinear time for analyzing the cluster structure of the graph are receiving growing interest. Two typ…