6 papers
Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle
Pan Peng, Kefan Yu
We prove that, for every fixed nonempty graph , induced--freeness is testable with queries on outerplanar graphs with no maximum-degree bound in the $…
Near-Optimal Four-Cycle Counting in Graph Streams
Sebastian Lüderssen, Stefan Neumann, Pan Peng
We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for -approximating the number of four-cycles using $\widetilde{O}(m/\s…
Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
Pan Peng, Yuyang Wang
We study \emph{local computation algorithms (LCAs)} for constructing spanning trees. In this setting, the goal is to locally determine, for each edge , whether it belong…
Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
Pan Peng, Christian Sohler, Yi Xu
Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a -clustering produced by SLC can be obtained by computing a min…
Streaming Max-Cut in General Metrics
Shaofeng H. -C. Jiang, Pan Peng, Haoze Wang
Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in \emph{gene…
Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
Weiming Feng, Zelin Li, Pan Peng
We study sublinear-time algorithms for solving linear systems , where is a diagonally dominant matrix, i.e., for all $i \in […