Graph Realization Programs
Graph Realization Problem (GRP) is the following:
Given a {0,1}matrix A,
decide whether A is a fundamental circuit matrix of a certain graph or not, and if so, construct such a graph.
The source codes below, written by Takahiro Ohto in 2003, implement two almost lineartime algorithms by Bixby and Wagner[1] and Fujishige[2].
See [3,4] for details.
Please check README file before using the programs.
Source Codes in J2SE 1.4
References
[1] R. E. Bixby and D. K. Wagner, An almost lineartime algorithm for graph realization, Mathematics of Operations Research, Vol.13 (1988), pp.99122.
[2] S. Fujishige, An efficient PGgraph algorithm for solving the graphrealization problem, Journal of Computer and System Sciences, Vol.21 (1980), pp.6386.
[3] T. Ohto, An Experimental Analysis of the BixbyWagner Algorithm for Graph Realization Problems (in Japanese), 2002AL84, pp.18.
[4] T. Ohto, Algorithms and Data Structures for Graph Realization Problems (in Japanese), Master Thesis, University of Tokyo, 2003.
DCP Project 
Naonori KAKIMURA (kakimura(a)math.keio.ac.jp) Replace '(a)' with '@'
modified on Apr. 2016.
