Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [adjacency-matrix]

The tag has no usage guidance.

2
votes
1answer
123 views

How to generate random adjacency matrix with given number of components in graph

I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph. For example, if I wanted to generate a graph of 50 ...
-2
votes
2answers
38 views

How to specify a robot go always right relative to itself from absolute perspective (north west east south)

I have a robot that has a start and goal position within a maze. Each point in the maze-grid is simply a Position object containing x and y. I need an algorithm that specifies the robot only moving to ...
0
votes
1answer
37 views

Manipulating Adjacency matrix

I have created an adjacency matrix which looks something like this ...
0
votes
2answers
50 views

Advantages (from a mathematical perspective) of representing data as symmetric matrices

From Wikipedia, a symmetric matrix is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing ...
2
votes
0answers
61 views

Eigenvalues of an induced subgraph of a random graph

Suppose $G$ is a random graph on $n$ vertices where each edge appears with probability half. Suppose someone looks at the resulting graph and chooses an arbitrary subset $W$ of vertices of size $k>\...
3
votes
1answer
78 views

Eigenvalue computation for large graph

Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it ...
1
vote
2answers
3k views

Time complexity of Prim's algorithm

There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix). As far as I have understood,that is because we have to ckeck all the nodes per every ...
0
votes
3answers
897 views

Traverse Matrix in Reverse Diagonal strips

I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated. So my question is, how would you write (in C) a function ...
11
votes
3answers
14k views

When are adjacency lists or matrices the better choice?

I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
1
vote
1answer
448 views

Adjacency matrix and recognizing hierarchy?

I'm currently learning about graphs and I have some questions regarding adjacency matrices. Given an arbitrary adjacency matrix: Is there any way to tell if that matrix represents a hierarchal graph ...
4
votes
1answer
728 views

Determining if a digraph has any vertex-disjoint cycle cover

Given a digraph, determine if the graph has any vertex-disjoint cycle cover. I understand that the permanent of the adjacency matrix will give me the number of cycle covers for the graph, which is 0 ...
1
vote
1answer
668 views

Implement multi-fragment heuristics for the traveling salesman problem

I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem. The algorithm is described here as follows: This seriation method re-...
0
votes
1answer
326 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
1k 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
1k 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
76 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
270 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
4k 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: ...
3
votes
1answer
2k 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
534 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
1k views

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

Consider the following adjacency matrix: ...
1
vote
1answer
241 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
89 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 ...
4
votes
2answers
8k 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
2k 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 ...