The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
33 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
3
votes
0answers
83 views

Graph partitioning problem

I am working on a solving a graph partitioning problem and have found a way to formulate it as a trace minimization. I am hoping this will allow me to relax the problem to a continuous one. I am ...
3
votes
2answers
1k views

What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
0
votes
1answer
462 views

Generating a adjacency matrix representing a DAG

Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph. Graph can be randomly created although I ...