607 questions
-1
votes
1
answer
100
views
Kruskal's Algorithm Minimum Spanning Tree (Disjoint Set data structure)
I would like to generate a minimum spanning tree for the following graph:
I am using the disjoint set data structure and I am having trouble with the union (Union Rank) operation.
The edges get ...
-2
votes
1
answer
132
views
Constrained MST: Find a spanning tree of weight ≤ T that minimizes the number of red edges
We are given an undirected graph ( G = (V, E) ), where:
( V ) is the set of vertices (or nodes),
( E ) is the set of edges.
Each edge ( e ∈ E ) has two attributes:
A weight ( w(e) ), which is a ...
- 103
1
vote
1
answer
308
views
Efficiently Find Approximate Minimum Spanning Tree of a Large Graph
I have a large number of nodes, ~25000, each with a 3D position.
I want to produce a sparsely connected graph, with edges given by the distance between nodes, for use in a GNN.
Algorithms to find the ...
- 23
4
votes
4
answers
385
views
Fast way of detecting outliers in 2D space
I have hundreds of millions of point clouds like the following:
I want to remove outliers 1, 2, 4, 5, 6, 7. The safest bet is to build a minimum spanning tree connecting all the points and remove ...
- 1,790
1
vote
1
answer
80
views
How to extract graph edges in a specific order from networkx?
I am trying to find the shortest path that passes through a set of points that are pretty much aligned. This needs to work in all directions, so I can't just sort them by x or y values.
The solution I ...
- 23
0
votes
1
answer
65
views
What is the complexity of the following code? Is it O(n^3log(n))?
What is the complexity of the following code? Is it O(n^3log(n))?
#G is an undirected dense graph, which has N vertices.
import networkx as nx
def cal_minimax_path_matrix(G):
MST = nx....
2
votes
1
answer
202
views
Minimum spanning tree variation for node-weighted graph
I'm trying to solve a variation of the minimum spanning tree problem; I have a graph where there are certain key nodes and optional nodes. Each optional node has a weight and we need to find a subset ...
- 116
2
votes
0
answers
224
views
Fastest way to run Steiner tree on large graph?
I have a very large graph (25GB, 35 million edges) and a collection of nodes. I want to find a tree that has all of those nodes; a tree that minimizes the number of edges but maximizes the number of ...
- 167
1
vote
2
answers
114
views
MST - Question with cycle in length 6 or less
I came across a question that I tried to solve by myself but I didn't come up with a satisfactory enough answer.
The Question:
Given an undirected graph G = (V, E) with weight function w: E->R ...
- 141
0
votes
0
answers
195
views
Manhattan Distance Minimum Spanning Tree
I'm working on a Steiner Tree algorithm for rectilinear graphs (Manhattan distance) and first of all I need to compute a minimum spanning tree as an upper bound, also with Manhattan distance. This is ...
0
votes
1
answer
143
views
Inconsistent results when using Scipy Minimum Spanning tree with sparse and dense inputs
I have the adjacency matrix of a graph stored as sparse scipy scr matrix. When I call the scipy.sparse.csgraph.minimum_spanning_tree function, my generated sparse array have too few non zero values ( ...
- 5
0
votes
1
answer
78
views
Proof in Minimum Spanning Trees(More of a mathematical problem)
As we know minimum spanning tree tries to achieve the "minimum" sum of weights of the tree.
Now my questions.
Using prim and kruskal algorithms,
1) If we change what we are trying to ...
0
votes
3
answers
118
views
Problem removing from Java-HashSet while implementing Kruskal's algorithm
in the following code I am trying to implement Kruskal's algorithm to compute the minimal spanning tree of a graph.
The problem is that removing sets from the connected components does not work ...
- 131
0
votes
1
answer
251
views
How to annotate distances of distance matrix to edges of a minimum-spanning-tree in R?
Aloha guys!
I am trying to create a Minimum-Spanning-Tree with ggplot, because I want to make use of the ggplot2 and especially ggnetwork functions like geom_edgelabel() to receive a sophisticated, ...
0
votes
0
answers
64
views
Prim’s MST Algorithm
I just finished an exercise on the application of Prim's theorem. However, I don't have the solution to this problem, but I found an answer in this exercise.
Could someone verify that the solution I ...
