Melvin's digital garden

Graph algorithms

CREATED: 200701060654

Undirected connectivity in log-space

O(sqrt(|V|)E) for matching by running BFS on all free vertices in parallel

MST in O(n)?

Alternative path - start and end in free vertex

Augmenting path - score of unmatch > match

Planar graph iff contains K_5 or K_(3,3)

A^k[i,j] is number of walks from v_i to v_j

Links to this note