Junxing Wang

activity

20172019

most citedGraph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm

12 citations · 17 across the 5 of their papers we have counts for

collaborators

Showing 2019Show all

2 papers · 1 filter

cs.DS2019★ 2 cited

Flowless: Extracting Densest Subgraphs Without Flow Computations

Digvijay Boob, Yu Gao, Richard Peng +4

We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…

cs.DS2019★ 3 cited

Near-Optimal Fully Dynamic Densest Subgraph

Saurabh Sawlani, Junxing Wang

We give the first fully dynamic algorithm which maintains a $(1 - ε)$ -approximate densest subgraph in worst-case time $poly (lo g n, ε^{- 1})$ per update. Dense subgraph discove…