Bisimplicial edges in bipartite graphs

M.J. Bomhoff, Bodo Manthey

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

79 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 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 languageUndefined
Title of host publicationProceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)
EditorsU. Faigle, R. Schrader, D. Herrmann
Place of PublicationCologne, Germany
PublisherUniversity of Cologne
Pages29-32
Number of pages4
ISBN (Print)not assigned
Publication statusPublished - 2010
Event9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 - University of Cologne, Cologne, Germany
Duration: 25 May 201027 May 2010

Publication series

Name
PublisherUniversity of Cologne

Workshop

Workshop9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010
CountryGermany
CityCologne
Period25/05/1027/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.