Computational implementation of Fujishige's graph realizability algorithm

Fujishige's PQ-graph algorithm is one of the most computationally efficient algorithms for testing the graph realizability of a (0,1) matrix E. This paper reports the first computational implementation of the algorithm. Computational testing, carried out on randomly generated matrices with up to 500 rows and 9000 columns, validates the almost linear time computational complexity of Fujishige's algorithm.