2 votes

Number of paths starting from a given edge using adjacency matrix

Given an adjacency matrix $\mathbf{A}$ representing $G$, the product $\mathbf{A}^{n - 1}$ will have the property that $\mathbf{A}_{ij} = k \iff$ there exists $k$ paths from vertex $i$ to vertex $j$. ...
codeing_monkey's user avatar
1 vote

DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Answer to question 1: I am not sure how the version of BFS with iterators would work. But it's also not clear why you would want to do that -- if you are after $O(V)$ space, the original algorithm ...
Tomek Czajka's user avatar
1 vote

Derandomization of vertex cover algorithm

Here are two possible derandomizations of the algorithm, with some caveats. One possible derandomized algorithm compute an optimal fractional solution $x^*$ to the standard linear-program (LP) ...
Neal Young's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible