17 citations · 25 across the 3 of their papers we have counts for
6 papers
Approximating the Spectrum of a Graph
David Cohen-Steiner, Weihao Kong, Christian Sohler +1
The spectrum of a network or graph with adjacency matrix , consists of the eigenvalues of the normalized Laplacian . This set of eigenvalue…
Estimating Graph Parameters from Random Order Streams
Pan Peng, Christian Sohler
We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate…
Testable Bounded Degree Graph Properties Are Random Order Streamable
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degre…
Clustering High Dimensional Dynamic Data Streams
Vladimir Braverman, Gereon Frahling, Harry Lang +2
We present data streaming algorithms for the -median problem in high-dimensional dynamic geometric data streams, i.e. streams allowing both insertions and deletions of points fr…
Theoretical Analysis of the -Means Algorithm - A Survey
Johannes Blömer, Christiane Lammersen, Melanie Schmidt +1
The -means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly diffic…
Testing Cluster Structure of Graphs
Artur Czumaj, Pan Peng, Christian Sohler
We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter , a -bounde…