Bisimplicial edges in bipartite graphs
Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that avoid turning zeroes into non-zeroes. We present a new deterministic algorithm to find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is O(nm) O ( n m ) , where n n is the number of vertices and m m is the number of edges. Furthermore, for any fixed p p and random bipartite graphs in the Gn,n,p G n , n , p model, the expected running-time of our algorithm is O(n2) O ( n 2 ) , which is linear in the input size.
bipartite graphs gaussian elimination algorithms random graphs