# Recognizing sparse perfect elimination bipartite graphs

M.J. Bomhoff

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

1 Citation (Scopus)

## Abstract

When applying Gaussian elimination to a sparse matrix, it is desirable to avoid turning zeros into nonzeros to preserve sparsity. Perfect elimination bipartite graphs are closely related to square matrices that Gaussian elimination can be applied to without turning any zero into a nonzero. Existing literature on the recognition of these graphs mainly focuses on time complexity. For $n \times n$ matrices with $m$ nonzero elements, the best known algorithm runs in time $O(n^3/\log n)$. However, the space complexity also deserves attention: it may not be worthwhile to look for suitable pivots for a sparse matrix if this requires $\Omega(n^2)$ space. We present two new recognition algorithms for 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 is easily adapted to run in time $O(n m)$
Original language Undefined Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011 A. Kulikov, N. Vereshchagin Heidelberg Springer 443-455 13 978-3-642-20711-2 https://doi.org/10.1007/978-3-642-20712-9_35 Published - Jun 2011 Computer Science – Theory and Applications - St. Petersburg, RussiaDuration: 14 Jun 2011 → 18 Jun 2011

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 6651 0302-9743 1611-3349

### Conference

Conference Computer Science – Theory and Applications 14/06/11 → 18/06/11 14-18 June 2011

## Keywords

• METIS-284944
• Perfect elimination – algorithms – bipartite graphs – sparse graphs
• EWI-21125
• IR-79141