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 languageUndefined
Title of host publicationComputer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011
EditorsA. Kulikov, N. Vereshchagin
Place of PublicationHeidelberg
PublisherSpringer
Pages443-455
Number of pages13
ISBN (Print)978-3-642-20711-2
DOIs
Publication statusPublished - Jun 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6651
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

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

Cite this

Bomhoff, M. J. (2011). Recognizing sparse perfect elimination bipartite graphs. In A. Kulikov, & N. Vereshchagin (Eds.), Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011 (pp. 443-455). (Lecture Notes in Computer Science; Vol. 6651). Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20712-9_35
Bomhoff, M.J. / Recognizing sparse perfect elimination bipartite graphs. Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011. editor / A. Kulikov ; N. Vereshchagin. Heidelberg : Springer, 2011. pp. 443-455 (Lecture Notes in Computer Science).
@inproceedings{f9e533cdd5f54ec5972a0d5d766a49f3,
title = "Recognizing sparse perfect elimination bipartite graphs",
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)$",
keywords = "METIS-284944, Perfect elimination – algorithms – bipartite graphs – sparse graphs, EWI-21125, IR-79141",
author = "M.J. Bomhoff",
note = "10.1007/978-3-642-20712-9_35",
year = "2011",
month = "6",
doi = "10.1007/978-3-642-20712-9_35",
language = "Undefined",
isbn = "978-3-642-20711-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "443--455",
editor = "A. Kulikov and N. Vereshchagin",
booktitle = "Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011",

}

Bomhoff, MJ 2011, Recognizing sparse perfect elimination bipartite graphs. in A Kulikov & N Vereshchagin (eds), Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011. Lecture Notes in Computer Science, vol. 6651, Springer, Heidelberg, pp. 443-455. https://doi.org/10.1007/978-3-642-20712-9_35

Recognizing sparse perfect elimination bipartite graphs. / Bomhoff, M.J.

Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011. ed. / A. Kulikov; N. Vereshchagin. Heidelberg : Springer, 2011. p. 443-455 (Lecture Notes in Computer Science; Vol. 6651).

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

TY - GEN

T1 - Recognizing sparse perfect elimination bipartite graphs

AU - Bomhoff, M.J.

N1 - 10.1007/978-3-642-20712-9_35

PY - 2011/6

Y1 - 2011/6

N2 - 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)$

AB - 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)$

KW - METIS-284944

KW - Perfect elimination – algorithms – bipartite graphs – sparse graphs

KW - EWI-21125

KW - IR-79141

U2 - 10.1007/978-3-642-20712-9_35

DO - 10.1007/978-3-642-20712-9_35

M3 - Conference contribution

SN - 978-3-642-20711-2

T3 - Lecture Notes in Computer Science

SP - 443

EP - 455

BT - Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011

A2 - Kulikov, A.

A2 - Vereshchagin, N.

PB - Springer

CY - Heidelberg

ER -

Bomhoff MJ. Recognizing sparse perfect elimination bipartite graphs. In Kulikov A, Vereshchagin N, editors, Computer Science – Theory and Applications: Proceedings 6th International Computer Science Symposium in Russia, CSR 2011. Heidelberg: Springer. 2011. p. 443-455. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-20712-9_35