Questions tagged [graph-theory]
A field of combinatorics relating to the study of vertices and the edges that connect them
88
questions
0
votes
0
answers
43
views
Rule-Based Link Prediction for Social Network [migrated]
Relevance to Site
I believe this question is suitable for the Computational Sciences Stack Exchange site as it pertains to the implementation of a graph algorithm. According to this widely accepted ...
0
votes
0
answers
71
views
How is kernel fusion done?
I have a computational graph (DAG) consisting of element-wise operations (potentially with broadcasting) and reshape/reduce operations (reshaping/sum/max). I'm trying to understand how vertical kernel ...
- 121
2
votes
1
answer
82
views
Computing the Fiedler vector of a large, sparse graph
I have a sparse, undirected and unweighted graph $G$ of size $n$, with $n$ on the order of say several million. I would like to compute the Fiedler vector $f$ of $G$, which is the eigenvector ...
- 503
0
votes
0
answers
62
views
Help with inferring Network topology from Spectral templates
I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
0
votes
1
answer
202
views
Problems on the algebraic theory of sparse matrices
I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
2
votes
0
answers
23
views
Code to list all maximal bicliques of a bipartite graph
We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
- 21
0
votes
0
answers
31
views
What do the Max-Cut algorithm graph cuts mean?
The max-cut algorithm divides a graph into 2 subsets, for instance:
While I understand the algorithm, I do not quite understand the meaning of the result. In the above picture, what does the ...
- 101
1
vote
0
answers
48
views
Vehicle passenger assignment with capacity constraint
Problem Background
I'm trying to find a solution to the following passenger matching problem:
The network is represented by graph $G=(V,E)$. $V$ is the set of nodes/stations. $p_{ij}$ is the profit of ...
- 11
9
votes
2
answers
2k
views
Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?
I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
2
votes
1
answer
177
views
Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices
is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices?
Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
- 91
1
vote
2
answers
870
views
How can I find the maximum equal-split flow of a network
I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint ...
0
votes
0
answers
80
views
How to distinguish primary hosts (stars) and orbiting satellites (planets) and tertiary bodies (moons) by their mass and trajectory?
I posted this question in the astronomy stackexchange. There are no responses, and it was suggested that I pose the question here. The "too long, didn't read" was taken from a comment, and ...
- 11
2
votes
0
answers
405
views
Mesh partitioning with METIS
I am trying to use METIS-5.1.0 edition in order to partion a FE mesh. For demostration purposes I created 2x2 rectangle mesh and tried to partition it. However, I notice a weird behaviour in my code. ...
- 481
0
votes
1
answer
32
views
Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?
I have a simple graph $G=(V,E)$ that is not necessarily a complete graph. If I compute the shortest distance between every pair of vertices (let say with Floyd-Warshall algorithm) I get a complete ...
- 21
3
votes
2
answers
211
views
Developing a meshfree contouring algorithm
I would like to find the contours of a scalar function $u(x,y)$ available as a discrete set of function values $u_i = u(x_i,y_i)$ over a scattered set of points $(x_i,y_i), i=1,...,N$.
In my case, the ...
- 617