# Tag Info

### Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
• 16.7k

### How can I quickly judge whether matrix A is the inverse matrix of B?

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random ...
• 616
Accepted

### In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n). That is wrong. It might work for a small ...
• 1,585

• 278k

### Arrays. Find row with most 1's, in O(n)

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked ...
• 30.7k

### Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can ...
• 743
Accepted

### $(max,+)$ matrix product with limited number of values

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. ...
• 8,303
Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual ...