Questions tagged [connected-components]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
11 views

Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
1
vote
1answer
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}$:- ...
2
votes
2answers
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 ...
1
vote
1answer
62 views

Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
4
votes
1answer
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 ...
2
votes
1answer
21 views

find the strong component containing the vertex v

I'm trying to solve this question for practising purposes: "Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, ...
2
votes
1answer
53 views

Fast algorithm for finding the size of each connected component in a graph of 2D points

I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all ...
2
votes
1answer
257 views

The number of connected components in the context of cyclomatic complexity

Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia): ...
1
vote
0answers
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 ...
0
votes
1answer
38 views

How can I examine the subnetworks of a nearly fully connected graph?

I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ...
0
votes
0answers
24 views

Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?

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 ...
3
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
129 views

Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex

Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to ...
0
votes
2answers
57 views

Finding connected components without building the graph first

What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in ...
0
votes
2answers
23 views

Doubt regarding strong component in a graph

I know that strong component in a graph means between any 2 vertices there should be bi-directional path. My doubt is cycle is always a strong component. can there be any other subgraph with some ...
1
vote
1answer
52 views

On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case. This is the algorithm: ...
1
vote
0answers
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?
3
votes
1answer
62 views

Equivalence of states between two “quasi-deterministic” strongly connected Büchi automata accepting the same $\omega$-language

Hope someone can point me to the right direction to solve this problem. Premise. I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, ...
6
votes
0answers
67 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,...
3
votes
1answer
643 views

Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
2
votes
2answers
265 views

Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

I asked this question on Stack Overflow, but I have not obtained an actual answer to the question. Tarjan's strongly connected components algorithm is stunningly beautiful, and inexpressible in a ...
2
votes
0answers
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 [...
2
votes
1answer
96 views

Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges. Is the following statement true? If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected....
2
votes
1answer
2k views

How to generate random adjacency matrix with given number of components in graph

I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph. For example, if I wanted to generate a graph of 50 ...