activity
20112026
most citedTestable Bounded Degree Graph Properties Are Random Order Streamable

8 citations · 24 across the 23 of their papers we have counts for

collaborators
Showing 2012Show all

2 papers · 1 filter

cs.DS2012

Testing Small Set Expansion in General Graphs

Angsheng Li, Pan Peng

We consider the problem of testing small set expansion for general graphs. A graph is a -expander if every subset of volume at most has conductance at least . Sma…

cs.DS2012

Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure

Angsheng Li, Pan Peng

We study the problem of finding and characterizing subgraphs with small \textit{bipartiteness ratio}. We give a bicriteria approximation algorithm \verb|SwpDB| such that if there e…