Testing Cluster Structure of Graphs
304 views · Published 28 March 2016 · 42:02 · Indexed 29 October 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Christian Sohler (TU Dortmund) Abstract: 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 eps, a d-bounded degree graph is defined to be (k,F)-clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least F and the (outer) conductance of each part is at most cϵ4F2, where c depends only on d,k. Our main result is a sublinear algorithm with the running time O((√n)poly(F,k,1/ϵ)) that takes asinput a graph with maximum degree bounded by d, parameters k, F, ϵ , and with probability at least 2/3, accepts the graph if it is (k,F)-clusterable and rejects the graph if it is ϵ-far from (k,F∗)-clusterable for F∗=cOF2ϵ4logn , where cO depends only on d,k.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...