Bisimplicial edges in bipartite graphs

M.J. Bomhoff; Bodo Manthey

Bisimplicial edges in bipartite graphs

M.J. Bomhoff
, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

290 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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is $O(n^2 \log n)$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.

Original language	Undefined
Title of host publication	Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)
Editors	U. Faigle, R. Schrader, D. Herrmann
Place of Publication	Cologne, Germany
Publisher	University of Cologne
Pages	29-32
Number of pages	4
ISBN (Print)	not assigned
Publication status	Published - 2010
Event	9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 - University of Cologne, Cologne, Germany Duration: 25 May 2010 → 27 May 2010

Publication series

Name
Publisher	University of Cologne

Workshop

Workshop	9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010
Country/Territory	Germany
City	Cologne
Period	25/05/10 → 27/05/10

Keywords

IR-75056
METIS-275736
Gaussian elimination
Probabilistic Analysis
Random matrices
EWI-18961
Bisimplicial edges

Access to Document

http://ctw.uni-koeln.de/CTW2010.pdf

1 Article

Bisimplicial edges in bipartite graphs
Bomhoff, M. & Manthey, B., 2013, In: Discrete applied mathematics. 161, 12, p. 1699-1706 8 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
2 Link opens in a new tab Citations (Scopus)

174 Downloads (Pure)

Cite this

@inproceedings{1d0c45778bea410c8fad8f4f9d3ed0d0,

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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is \$O(n\textasciicircum{}2 \textbackslash{}log n)\$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.",

keywords = "IR-75056, METIS-275736, Gaussian elimination, Probabilistic Analysis, Random matrices, EWI-18961, Bisimplicial edges",

author = "M.J. Bomhoff and Bodo Manthey",

year = "2010",

language = "Undefined",

isbn = "not assigned",

publisher = "University of Cologne",

pages = "29--32",

editor = "U. Faigle and R. Schrader and D. Herrmann",

booktitle = "Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)",

note = "9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 ; Conference date: 25-05-2010 Through 27-05-2010",

}

Bomhoff, MJ & Manthey, B 2010, Bisimplicial edges in bipartite graphs. in U Faigle, R Schrader & D Herrmann (eds), Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). University of Cologne, Cologne, Germany, pp. 29-32, 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010, Cologne, Germany, 25/05/10. <http://ctw.uni-koeln.de/CTW2010.pdf>

Bisimplicial edges in bipartite graphs. / Bomhoff, M.J.; Manthey, Bodo.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010). ed. / U. Faigle; R. Schrader; D. Herrmann. Cologne, Germany: University of Cologne, 2010. p. 29-32.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Bisimplicial edges in bipartite graphs

AU - Bomhoff, M.J.

AU - Manthey, Bodo

PY - 2010

Y1 - 2010

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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is $O(n^2 \log n)$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.

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 nd such edges in bipartite graphs. The expected time complexity of our new algorithm is $O(n^2 \log n)$ on random bipartite graphs in which each edge is present with a fixed probability p, a polynomial improvement over the fastest algorithm found in the existing literature.

KW - IR-75056

KW - METIS-275736

KW - Gaussian elimination

KW - Probabilistic Analysis

KW - Random matrices

KW - EWI-18961

KW - Bisimplicial edges

M3 - Conference contribution

SN - not assigned

SP - 29

EP - 32

BT - Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)

A2 - Faigle, U.

A2 - Schrader, R.

A2 - Herrmann, D.

PB - University of Cologne

CY - Cologne, Germany

T2 - 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010

Y2 - 25 May 2010 through 27 May 2010

ER -