Questions tagged [connected-components]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
151 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 ...
Brett's user avatar
  • 1
2 votes
0 answers
61 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 ...
Nathaniel's user avatar
  • 13.9k
1 vote
1 answer
134 views

Boolean constraints for a connected component of a graph

Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\{v \mid ...
D.W.'s user avatar
  • 158k
0 votes
1 answer
31 views

How reversing the edges of the graph not altering the original conditions?

I was going through the main idea of solution to this problem. I could not assimilate the idea of reversing the edges and then using that graph to check if node 1 is reachable from all others. How ...
harshmangalamv's user avatar
1 vote
1 answer
67 views

Infinite Graph with Finite Degree

Let $G$ be an undirected graph with an infinite number of vertices (and edges), and assume it is connected in the sense every $u,v$ have at least one path connecting them. Assume each vertex has a ...
Dan D-man's user avatar
  • 514
0 votes
1 answer
34 views

Find connected components in a graph of computer network with parallel pairwise tests

I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K<=N, K unknown). I can test if a given pair is connected. In each step in time, I can run ...
Gili Nachum's user avatar
1 vote
0 answers
126 views

Reverse one edge to make the most expansive strongly connected component

Problem statement We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. ...
tomashauser's user avatar
2 votes
1 answer
630 views

Deciding if a graph is "Single Connected"

The definition of "Single Connected" is that for every $u,v \in V$ there is at most a single simple path from $u$ to $v$, and at most a single simple path from $v$ to $u$. The objective is ...
Aishgadol's user avatar
  • 345
1 vote
2 answers
144 views

A graph is strongly connected iff every non-trivial cut contains an edge

As the title states, I am asked to prove that a directed graph $G=(V,E)$ is strongly connected iff for all non-empty subsets $\emptyset \neq S \subset V$, the cut $\delta(S) \neq\emptyset$, where $$\...
Aishgadol's user avatar
  • 345
1 vote
1 answer
167 views

(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges

I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs. Specifically, I've been trying ...
Shay's user avatar
  • 113
3 votes
1 answer
118 views

Efficiently determine which nodes should leave a graph while maintaining connectedness

Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example: If a node has weight -1, it is "happy", and cannot be kicked out of the graph. If a ...
416E64726577's user avatar
2 votes
1 answer
90 views

Make maze connected by removing internal walls

Recently I've stumbled upon a strange graph problem. Here is a brief description. Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
stackoverload's user avatar
0 votes
0 answers
28 views

Graph with constant edge connectivity that remains connected after edge removals

I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
NiRvanA's user avatar
  • 159
0 votes
2 answers
538 views

Algorithm for Getting Largest Connected Component From List of Touching Pairs

I have a program which finds the touching pairs of a given value in a binary image. For example, consider the below image: ...
Luca Passariello's user avatar
1 vote
0 answers
52 views

Finding highly-connected regions of graphs

I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria. To ...
Gabriel's user avatar
  • 11
0 votes
0 answers
67 views

I do not understand a way of proving the correctness of the algorithm to compute the Strongly Connected Components

"Introduction to algorithms" also known as CLRS, proves the correctness of the algorithm to compute the Strongly Connected Components in two ways, one of which is Here is another way to ...
AlessandroF's user avatar
2 votes
0 answers
90 views

How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?

Let's have a standard topological ordering algorithm (from CLRS): ...
AlessandroF's user avatar
2 votes
1 answer
520 views

What is the relation between Topological Sort and Strongly Connected Components?

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex. I find difficult to find an explaination because ...
AlessandroF's user avatar
2 votes
1 answer
311 views

Minimum vertices to remove from a graph so that no path exists between two given vertices anymore

Given an undirected graph $G=\{V, E\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $...
Arkajyoti Banerjee's user avatar
0 votes
3 answers
749 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) ...
user avatar
3 votes
2 answers
901 views

Efficiently check if removing an edge splits a strongly connected component

I have a strongly connected component (SCC) of $n$ vertices. Let $n_1n_2$ be an edge between two vertices $n_1$ and $n_2$ in this SCC. Is there an efficient algorithm to check if removing the edge $...
thambi's user avatar
  • 123
1 vote
1 answer
34 views

Enumerate all connected components that could be created from removing k edges?

I have a simple connected undirected graph $G=(V, E)$ and I would like to enumerate all possible connected components that arise from removing $k$ edges in $E$. A naive way is to remove each $k$-tuple ...
Eric J's user avatar
  • 211
1 vote
1 answer
237 views

Minimal cut of a directed graph such that disjoint elements are strongly connected

Given an arbitrary directed graph $G$ (which may not necessarily be connected) find a minimum set of edges $S\subseteq E$ such that every disjoint component of $G(V,E\cap S')$ is strongly connected. A ...
grand aneww's user avatar
2 votes
1 answer
158 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, ...
Mika2019's user avatar
3 votes
1 answer
658 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 ...
fuzzypixelz's user avatar
1 vote
1 answer
555 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 ...
pk00's user avatar
  • 27
4 votes
1 answer
2k 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): ...
Ilya Loskutov's user avatar
1 vote
0 answers
60 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 ...
Sergey Grigoryants's user avatar
0 votes
0 answers
171 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 ...
Nascimento de Cos's user avatar
0 votes
1 answer
72 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 ...
Ameet Rahane's user avatar
3 votes
0 answers
44 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 ...
Radio Controlled's user avatar
2 votes
0 answers
66 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 ...
mjfneto's user avatar
  • 21
0 votes
1 answer
303 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 ...
Mamun's user avatar
  • 87
0 votes
2 answers
100 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 ...
Radio Controlled's user avatar
0 votes
2 answers
30 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 ...
Nascimento de Cos's user avatar
1 vote
1 answer
202 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: ...
carlos palma's user avatar
1 vote
0 answers
79 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?
Shadab Ahmed's user avatar
3 votes
1 answer
84 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$, ...
Davide's user avatar
  • 33
7 votes
0 answers
285 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,...
Amelio Vazquez-Reina's user avatar
2 votes
1 answer
181 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}$:- ...
rajdeep dhingra's user avatar
3 votes
2 answers
231 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 ...
Hypnotic's user avatar
4 votes
1 answer
253 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 ...
Michaël's user avatar
  • 141
4 votes
1 answer
2k 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 ...
Otto Rocket's user avatar
2 votes
2 answers
429 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 ...
isekaijin's user avatar
  • 405
3 votes
0 answers
34 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 [...
Ferry T's user avatar
  • 31
2 votes
1 answer
302 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....
Sudix's user avatar
  • 709
2 votes
1 answer
3k 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 ...
Sabarna Hazra's user avatar