Recognizing sparse perfect elimination bipartite graphs

Bomhoff, Matthijs (2011) Recognizing sparse perfect elimination bipartite graphs. In: Computer Science – Theory and Applications, 14-18 June 2011, St. Petersburg, Russia.

PDF
Restricted to UT campus only: Request a copy
238Kb

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)$
Item Type:	Conference or Workshop Item
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79141
Official URL:	http://dx.doi.org/10.1007/978-3-642-20712-9_35
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page