Estimating the number of connected components in sublinear time

• Published in: Information processing letters 2014-11, Vol.114 (11), p.639-642
• Main Authors: Berenbrink, Petra, Krayenhoff, Bruce, Mallmann-Trenn, Frederik
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation algorithms; Computer vision; Connected components; Data processing; Estimating techniques; Graph algorithms; Graph theory; Graphs; Labelling; Mathematical analysis; Mathematical problems; Running; Studies; Sublinear time algorithms
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2014.05.008

We present an algorithm that estimates the number of connected components of a graph over n vertices within an additive error of εn in (sublinear) time O(1ε2log(1ε)). A connected component C is the maximal subset of nodes of an undirected graph G such that for any two nodes in C there is path connecting. We consider graphs without multiple edges. The Connected Component Problem is well-known and amongst the first topics taught in graph theory. The number of connected components can be used to calculate the weight of the minimum spanning tree [1]. Moreover, the study of connected components finds its application in Connected-component labelling, which is used in computer vision. An algorithm runs in sublinear time if its running time is o(n) for an input of size n. So far, the best known algorithm was provided by [1]. Their running time is O(dε−2log(dε)) where d is the average degree. •We present an algorithm that estimates the number of connected components of a graph.•Our running time depends only on the additive approximation.•So far, the best known running time depends on the average degree.•The number of connected components can be used to calculate the weight of the MST.