Recognizing sparse perfect elimination bipartite graphs

M.J. Bomhoff

Research output: Book/ReportReportProfessional

108 Downloads (Pure)


When applying Gaussian elimination to a sparse matrix, it is desirable to avoid turning zeros into non-zeros to preserve the sparsity. The class of perfect elimination bipartite graphs is closely related to square matrices that Gaussian elimination can be applied to without turning any zero into a non-zero. Existing literature on the recognition of this class and finding suitable pivots mainly focusses on time complexity. For $n \times n$ matrices with m non-zero elements, the currently best known algorithm has a time complexity of $O(n^3/\log n)$. However, when viewed from a practical perspective, the space complexity also deserves attention: it may not be worthwhile to look for a suitable set of pivots for a sparse matrix if this requires $\Omega(n^2)$ space. We present two new algorithms for the recognition of sparse instances: one with a $O(n m)$ time complexity in $\Theta(n^2)$ space and one with a $O(m^2)$ time complexity in $\Theta(m)$ space. Furthermore, if we allow only pivots on the diagonal, our second algorithm can easily be adapted to run in time $O(n m)$.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages12
Publication statusPublished - Dec 2010

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850


Dive into the research topics of 'Recognizing sparse perfect elimination bipartite graphs'. Together they form a unique fingerprint.
  • Recognizing sparse perfect elimination bipartite graphs

    Bomhoff, M. J., Jun 2011, Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011. Kulikov, A. & Vereshchagin, N. (eds.). Heidelberg: Springer, p. 443-455 13 p. (Lecture Notes in Computer Science; vol. 6651).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Citation (Scopus)
    1 Downloads (Pure)

Cite this