The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
28 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 ...
106 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 ...
36 views

### Min-plus matrix and Shortest path variation

I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes. One method is : let ...
32 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 ...
269 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 ...
266 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 <...
190 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 ...
25 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 ...
4k 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 ...
2k 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 ...
39 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 ...
82 views

I have created an adjacency matrix which looks something like this ...
397 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 ...