### Abstract

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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is $O(n^2 \log n)$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010) |

Editors | U. Faigle, R. Schrader, D. Herrmann |

Place of Publication | Cologne, Germany |

Publisher | University of Cologne |

Pages | 29-32 |

Number of pages | 4 |

ISBN (Print) | not assigned |

Publication status | Published - 2010 |

Event | 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 - University of Cologne, Cologne, Germany Duration: 25 May 2010 → 27 May 2010 |

### Publication series

Name | |
---|---|

Publisher | University of Cologne |

### Workshop

Workshop | 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 |
---|---|

Country | Germany |

City | Cologne |

Period | 25/05/10 → 27/05/10 |

### Keywords

- IR-75056
- METIS-275736
- Gaussian elimination
- Probabilistic Analysis
- Random matrices
- EWI-18961
- Bisimplicial edges

## Cite this

Bomhoff, M. J., & Manthey, B. (2010). Bisimplicial edges in bipartite graphs. In U. Faigle, R. Schrader, & D. Herrmann (Eds.),

*Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)*(pp. 29-32). Cologne, Germany: University of Cologne.