International Journal of Mathematics and Mathematical Sciences 
Volume 18 (1995), Issue 2, Pages 299-304
doi:10.1155/S0161171295000378

Algorithmic aspects of bipartite graphs

Mihály Bakonyi1 and Erik M. Varness2

 1Department of Mathematics, Georgia State University, Atlanta 30303, GA, USA
2Department of Mathematics, Valparaiso University, Valparaiso 46383, Indiana, USA
Received 19 March 1993

Abstract

We generalize previous work done by Donald J. Rose and Robert E. Tarjan [2], who developed efficient algorithms for use on directed graphs. This paper considers an edge elimination process on bipartite graphs, presenting several theorems which lead to an algorithm for computing the minimal fill-in of a given ordered graph.