The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
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 ...
19 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 ...
76 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 <...
90 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 ...
21 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 ...
2k 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 ...
1k 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 ...
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 ...
71 views

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