Bisimplicial edges in bipartite graphs

Matthijs Bomhoff; Bodo Manthey

doi:10.1016/j.dam.2011.03.004

Bisimplicial edges in bipartite graphs

Matthijs Bomhoff
, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

153 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 find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is $O(nm)$, where $n$ is the number of vertices and $m$ is the number of edges. Furthermore, for any fixed $p$ and random bipartite graphs in the $G_{n,n,p}$ model, the expected running-time of our algorithm is $O(n^2)$, which is linear in the input size.

Original language	English
Pages (from-to)	1699-1706
Number of pages	8
Journal	Discrete applied mathematics
Volume	161
Issue number	12
DOIs	https://doi.org/10.1016/j.dam.2011.03.004
Publication status	Published - 2013

Keywords

Gaussian elimination
Bisimplicial edges
Random graphs

Access to Document

10.1016/j.dam.2011.03.004Licence: Other

bisimplicialFinal published version, 321 KBLicence: Other

2 Citations
1 Conference contribution

Bisimplicial edges in bipartite graphs
Bomhoff, M. J. & Manthey, B., 2010, Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). Faigle, U., Schrader, R. & Herrmann, D. (eds.). Cologne, Germany: University of Cologne, p. 29-32 4 p.
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

File

Cite this

@article{a9b4be9ca4c644df880a1bb6cdbe7783,

title = "Bisimplicial edges in bipartite graphs",

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 find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is \$O(nm)\$, where \$n\$ is the number of vertices and \$m\$ is the number of edges. Furthermore, for any fixed \$p\$ and random bipartite graphs in the \$G\_\{n,n,p\}\$ model, the expected running-time of our algorithm is \$O(n\textasciicircum{}2)\$, which is linear in the input size.",

keywords = "Gaussian elimination, Bisimplicial edges, Random graphs",

author = "Matthijs Bomhoff and Bodo Manthey",

year = "2013",

doi = "10.1016/j.dam.2011.03.004",

language = "English",

volume = "161",

pages = "1699--1706",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "12",

}

TY - JOUR

T1 - Bisimplicial edges in bipartite graphs

AU - Bomhoff, Matthijs

AU - Manthey, Bodo

PY - 2013

Y1 - 2013

N2 - 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 find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is $O(nm)$, where $n$ is the number of vertices and $m$ is the number of edges. Furthermore, for any fixed $p$ and random bipartite graphs in the $G_{n,n,p}$ model, the expected running-time of our algorithm is $O(n^2)$, which is linear in the input size.

AB - 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 find such edges in bipartite graphs. Our algorithm is very simple and easy to implement. Its running-time is $O(nm)$, where $n$ is the number of vertices and $m$ is the number of edges. Furthermore, for any fixed $p$ and random bipartite graphs in the $G_{n,n,p}$ model, the expected running-time of our algorithm is $O(n^2)$, which is linear in the input size.

KW - Gaussian elimination

KW - Bisimplicial edges

KW - Random graphs

U2 - 10.1016/j.dam.2011.03.004

DO - 10.1016/j.dam.2011.03.004

M3 - Article

SN - 0166-218X

VL - 161

SP - 1699

EP - 1706

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 12

ER -

Bisimplicial edges in bipartite graphs

Abstract

Keywords

Access to Document

Fingerprint

Research output

Bisimplicial edges in bipartite graphs

Cite this