Bisimplicial edges in bipartite graphs

Matthijs Bomhoff, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
89 Downloads (Pure)

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 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.
Original languageEnglish
Pages (from-to)1699-1706
Number of pages8
JournalDiscrete applied mathematics
Volume161
Issue number12
DOIs
Publication statusPublished - 2013

Keywords

  • Gaussian elimination
  • Bisimplicial edges
  • Random graphs

Fingerprint

Dive into the research topics of 'Bisimplicial edges in bipartite graphs'. Together they form a unique fingerprint.
  • Bisimplicial edges in bipartite graphs

    Bomhoff, M. J. & Manthey, B., 2010, Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). Faigle, U., Schrader, R. & Herrmann, D. (eds.). Cologne, Germany: University of Cologne, p. 29-32 4 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    File

Cite this