4 citations · 8 across the 8 of their papers we have counts for
9 papers
Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle
Pan Peng, Jiapeng Zhang
Motivated by applications in crowdsourced entity resolution in database, signed edge prediction in social networks and correlation clustering, Mazumdar and Saha [NIPS 2017] propose…
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
Jakob Bossek, Frank Neumann, Pan Peng +1
We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the…
GSF-locality is not sufficient for proximity-oblivious testing
Isolde Adler, Noleen Köhler, Pan Peng
In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on…
Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
Monika Henzinger, Pan Peng
We give two fully dynamic algorithms that maintain a -approximation of the weight of a minimum spanning forest (MSF) of an -node graph with edges weight…
On Testability of First-Order Properties in Bounded-Degree Graphs
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…
Augmenting the Algebraic Connectivity of Graphs
Bogdan-Adrian Manghiuc, Pan Peng, He Sun
For any undirected graph and a set of candidate edges with , the -spectral augmentability problem is to find a set of edges from…