Questions tagged [adjacency-matrix]
The adjacency-matrix tag has no usage guidance.
36 questions
1
vote
0
answers
32
views
Efficiently generating the smallest directed graph subject to degree constraints that yields a requested flow
Given two (small-ish) sequences $I$ and $O$ of rational numbers with $\sum_{x \in I}x=\sum_{y \in O}y$, generate a directed graph $G = (V,E)$ with minimum $|V|$ that respects the following:
$|I|$ ...
- 11
4
votes
2
answers
917
views
How to represent BFS and DFS between adjacency matrix and list?
I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. ...
- 43
1
vote
1
answer
112
views
Do Adjacency Lists from Binary Trees go both ways?
From my reading and research it appears it's one way, however my lecturer states that it goes both ways in his examples.
Let me show you what i mean by this.
He claims that a binary tree built from a ...
- 11
1
vote
2
answers
112
views
Number of paths starting from a given edge using adjacency matrix
I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that ...
11
votes
0
answers
135
views
Min-eigenvalue bound for a random d-regular graph
I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
- 156
0
votes
0
answers
36
views
Question regarding a particular type of graph
Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if ...
- 249
0
votes
0
answers
2k
views
Time complexity for computing the highest degree vertex
Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format.
What is the time complexity of finding the highest-degree vertex, assuming the ...
- 101
3
votes
0
answers
641
views
When are adjacency lists better than sparse matrices?
I saw several questions discussion the benefits of adjacency lists over matrices to represent a sparse undirected graph. On the other hand, none of them discuss sparse matrix representations such as <...
- 131
3
votes
1
answer
401
views
Calculate boolean matrix multiplication (BMM) using transitive closure
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...
- 31
0
votes
0
answers
44
views
Decomposition of graph to subgraphs according to parallel edges
I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges.
If N parallel ...
15
votes
3
answers
10k
views
Intuition behind eigenvalues of an adjacency matrix
I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a ...
- 359
2
votes
1
answer
3k
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
2
answers
44
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 ...
- 1
0
votes
1
answer
128
views
Manipulating Adjacency matrix
I have created an adjacency matrix which looks something like this
...
- 3
0
votes
2
answers
788
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,295
2
votes
0
answers
131
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>\...
- 464
3
votes
1
answer
486
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 ...
- 31
1
vote
2
answers
8k
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 ...
- 629
0
votes
6
answers
5k
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 ...
23
votes
3
answers
44k
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 ...
- 351
2
votes
1
answer
968
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 ...
- 125
4
votes
1
answer
2k
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 ...
- 43
1
vote
1
answer
2k
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-...
user20691
0
votes
1
answer
908
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 ...
- 1
0
votes
0
answers
2k
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]:
...
- 101
-2
votes
1
answer
3k
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 ...
- 101
1
vote
0
answers
86
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 ...
user39969
0
votes
2
answers
701
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 ...
- 143
2
votes
1
answer
7k
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:
...
- 233
4
votes
1
answer
3k
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 ...
- 181
0
votes
2
answers
863
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 ...
- 475
-2
votes
1
answer
2k
views
How to find number of paths between 2 nodes of a certain length [duplicate]
Consider the following adjacency matrix:
...
- 169
1
vote
1
answer
1k
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?
- 859
1
vote
0
answers
108
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 ...
- 111
7
votes
2
answers
18k
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 I ...
- 223
0
votes
1
answer
4k
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 ...
- 297