3 papers
cs.DS2021
Local Algorithms for Estimating Effective Resistance
Pan Peng, Daniel Lopatta, Yuichi Yoshida +1
Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and netwo…
cs.NE2021
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…
cs.CC2021
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…