Questions tagged [connected-components]

The tag has no usage guidance.

48 questions
Filter by
Sorted by
Tagged with
26 views

Kruskal's algorithm including an edge

I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
• 101
212 views

Tseitin formula on 2-connected graph

How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a ...
66 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
• 15.9k
1 vote
202 views

923 views

O(m) time algorithm to check for a strongly connected graph

Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex. what's a good algorithm to check for this that runs in O(m) ...