# Questions tagged [connected-components]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
68 views

### When would Kosaraju's algorithm be a better choice than Tarjan's for strongly connected components?

I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack,...
101 views

### Computing a pre-topological sort using a BFS/a queue

Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
26 views

### Components of subset partial order

Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper. But is there any work on algorithms ...
56 views

### But How do it Remembers?*

It is a joke with the title of a book I am reading: "But how do it Know? - The Basic Principles of Computers to Anyone". The author is explaining a basic unit of memory with NAND gates: I ...
108 views

### Articulation points (or cut vertices), but only subset of vertices need to be connected

I know we can find all articulation points efficiently in a graph using DFS. But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is ...
24 views

### Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees

I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
36 views

### Graph dynamic connectivity

Let $G=(V,E)$ be an undirected graph. I would like to maintain information about the connected components of this graph(I want to be able to tell in what component particular node is lying). The graph ...
28 views

### Remove vertices to get k-connected components

In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
81 views

### Bridges and Edge Disjoint Paths

So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ? $\text{My Attempt at the Proof}$:- ...
We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time ...