TY - JOUR
T1 - Bisimplicial edges in bipartite graphs
AU - Bomhoff, Matthijs
AU - Manthey, Bodo
PY - 2013
Y1 - 2013
N2 - 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)$, where $n$ is the number of vertices and $m$ is the number of edges. Furthermore, for any fixed $p$ and random bipartite graphs in the $G_{n,n,p}$ model, the expected running-time of our algorithm is $O(n^2)$, which is linear in the input size.
AB - 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)$, where $n$ is the number of vertices and $m$ is the number of edges. Furthermore, for any fixed $p$ and random bipartite graphs in the $G_{n,n,p}$ model, the expected running-time of our algorithm is $O(n^2)$, which is linear in the input size.
KW - Gaussian elimination
KW - Bisimplicial edges
KW - Random graphs
U2 - 10.1016/j.dam.2011.03.004
DO - 10.1016/j.dam.2011.03.004
M3 - Article
SN - 0166-218X
VL - 161
SP - 1699
EP - 1706
JO - Discrete applied mathematics
JF - Discrete applied mathematics
IS - 12
ER -