1
$\begingroup$

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found.

Suppose I only have an incidence matrix as a representation of a graph. Is there another algorithm (faster perhaps) to find the largest component by taking advantage of the structure of the incidence matrix?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

There could be an algorithm that would be useful for a sparse graph that takes $O(|E|)$ time. In that case you would want to just have a list of edges and would not want to have to scan an adjacency matrix. This would be the fastest possible in order to be certain you've found all components.

$\endgroup$
3
  • $\begingroup$ How would I use the list of edges efficiently to find the components? $\endgroup$
    – user100554
    Commented Nov 14, 2014 at 20:32
  • $\begingroup$ Build a smaller graph that contains only the vertices that are contained in an edge and use BFS. There's only an improvement if there are a lot of vertices that aren't contained in any edge. If every vertex is in an edge, BFS is the best you can do no matter what the representation. $\endgroup$
    – Matt Samuel
    Commented Nov 14, 2014 at 20:35
  • $\begingroup$ There is no sparsity in my graph, every vertex is in an edge. Oh well, thanks anyway. $\endgroup$
    – user100554
    Commented Nov 14, 2014 at 22:10
1
$\begingroup$

From the incidence matrix, you can obtain the Laplacian matrix, then from there, you know that the null space of the Laplacian gives you the connected components of your graph.

$\endgroup$

You must log in to answer this question.