The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
42 views

Does the order matter in the adjacency matrix?

I have nodes a, b , c,d,N, and e in an adjacency matrix. If I follow the order as a,b,c,d,N,and,e , I get 100010(the question does not matter because I'm asking about the order) for b.But if I follow ...
0
votes
0answers
61 views

Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

Let's say for the following weighted, undirected graph: I am given the adjacency matrix A[5][5]: ...
-2
votes
1answer
90 views

How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix) [closed]

Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)? similar question ...
1
vote
0answers
32 views

Relation between determinant and matrix multiplication

I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be ...
0
votes
2answers
28 views

Can adjacency lists be used in directed graphs?

I've been reading: https://en.wikipedia.org/wiki/Adjacency_list It says that that graph can be constructed with the list $\{b, c\}, \{a, c\}, \{a, b\}$. However, what if I wanted to construct a ...
2
votes
1answer
503 views

Remove Edge From Adjacency List

INPUT: weighted undirected graph in the form of adjacency list OUTPUT: adjacency list without the edge e Naive approach is: ...
2
votes
1answer
288 views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
0
votes
2answers
203 views

scale-free networks and adjacency matrix

Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the ...
-2
votes
1answer
237 views

How to find number of paths between 2 nodes of a certain length [duplicate]

Consider the following adjacency matrix: ...
1
vote
1answer
99 views

Are all adjacency matrices represented by 0 and 1s? [closed]

Are there any cases when adjacency matrix should have entries other than 0 and 1?
1
vote
0answers
55 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
2answers
3k 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
1k 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 ...