Cycle basis is a useful tool for graph analysis and algorithms. One well-known
method to obtain cycle basis of a (connected) graph is to generate the set of all fundamental
cycles with respect to some spanning tree. For a given graph, finding the
spanning tree for which the sum of the lengths of all the fundamental cycles is the
smallest is called the Minimum-Length Fundamental-Cycle Set problem (MFS). It is
known to be NP-complete. Suboptimal solution to the MFS problem has been applied
to speed up the algorithm for generating minimal perfect hash function. In this
paper we propose a new heuristic for the MFS problem. We also implemented the
new heuristic and the best published heuristic on a massively parallel SIMD machine
(MasPar MP-1). Programming on the MasPar machine involved a careful implementation
of PRAM-type algorithms by exploiting the built-in routines. We compare the
two heuristics on graphs of varying orders and densities; the largest of them has 8192
nodes and about 16 million edges. The runtime and the scalability issues of our parallel
implementations are also addressed.