Pan Peng

most citedMore Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization

2 citations · 3 across the 5 of their papers we have counts for

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2020

Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest

Monika Henzinger, Pan Peng

We give two fully dynamic algorithms that maintain a $(1 + ε)$ -approximation of the weight $M$ of a minimum spanning forest (MSF) of an $n$ -node graph $G$ with edges weight…

cs.DS2020

Augmenting the Algebraic Connectivity of Graphs

Bogdan-Adrian Manghiuc, Pan Peng, He Sun

For any undirected graph $G = (V, E)$ and a set $E_{W}$ of candidate edges with $E \cap E_{W} = \emptyset$ , the $(k, γ)$ -spectral augmentability problem is to find a set $F$ of $k$ edges from…

cs.DS2020

Average Sensitivity of Spectral Clustering

Pan Peng, Yuichi Yoshida

Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in tho…

cs.DS2020

Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time

Hendrik Fichtenberger, Mingze Gao, Pan Peng

We present a simple sublinear-time algorithm for sampling an arbitrary subgraph $H$ \emph{exactly uniformly} from a graph $G$ with $m$ edges, to which the algorithm has access by p…