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 linear-time 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 linear-time algorithm for graph realization, Mathematics of Operations Research, Vol.13 (1988), pp.99-122.
[2] S. Fujishige, An efficient PG-graph algorithm for solving the graph-realization problem, Journal of Computer and System Sciences, Vol.21 (1980), pp.63-86.
[3] T. Ohto, An Experimental Analysis of the Bixby-Wagner Algorithm for Graph Realization Problems (in Japanese), 2002-AL-84, pp.1-8.
[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.
|