Questions tagged [connected-components]
The connected-components tag has no summary.
50 questions
3 votes
0 answers
66 views
reference for SAT formula for connectedness
SAT formulas for connectedness of a set of nodes in a graph can be constructed, basically by specifying the distance of each node to a source node, see for example the answers here: Boolean ...
- 31.6k
1 vote
1 answer
56 views
Detecting Hole Creation in a Cellular Automaton
I'm working on a cellular automaton related to Diffusion-Limited aggregation where the simulation runs on a grid. Each cell is either EMPTY or FULL. Once a cell transitions from EMPTY to FULL (...
- 13
1 vote
0 answers
74 views
Version of SSSP
Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function. Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes....
- 189
2 votes
1 answer
278 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 ...
user167124
2 votes
0 answers
95 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 ...
- 18.5k
2 votes
1 answer
371 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.♦
- 169k
0 votes
1 answer
66 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 ...
1 vote
1 answer
104 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 ...
- 544
0 votes
1 answer
87 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 ...
- 101
1 vote
0 answers
216 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. ...
- 147
2 votes
1 answer
1k 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 ...
- 377
1 vote
2 answers
270 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 $$\...
- 377
1 vote
1 answer
338 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 ...
- 113
3 votes
1 answer
150 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 ...
- 133
2 votes
1 answer
193 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 "+", "-&...
- 123