Questions tagged [subgraphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
27 views

Find subgraphs that can only be reached by two nodes

I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only ...
2
votes
0answers
23 views

How to calculate delta Q (modularity increase matrix) in graphs?

I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
2
votes
1answer
22 views

Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?

MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem is to find a ...
0
votes
1answer
76 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 ...
1
vote
1answer
83 views

Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?

Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$...