Random spanning trees of bipartite graphs

Question

I'm working on making some code using metaheuristics for finding good solutions to the Fixed Charge Transportation Problem (FCTP).

The problem I'm having is to generate a starting solution, based on finding a spanning tree for the underlying bipartite graph.

I want it to be a random spanning tree, so that I can run the procedure on the same problem multiple times, possibly getting different solutions.

I'm having some difficulties doing this. The approach I've gone for so far is to make a random permutation of the arcs, then iterate through this list, sequentially putting them into basis if it won't create a cycle.

I need to find a fast method to check if including an arc will create a cycle. I don't want to "brute force" it, since this approach could take a large amount of time, given big problem instances.

Given that A is an array with a random permutation of the arcs, how would you go around making a selection procedure?

I've been working on this for a couple of hours now, and nothing I've tried has worked, most of it being nonsensical when it came to application...

Answer 1

Kruskals Algorithm is used for finding the minimum spanning tree. The fast-cycle detection is not actually part of Kruskals algorithm. The algorithm will work with a data structure that is able to find cycles fast as well as with a slow naive attempt (however the complexity will be different).

However Kruskals Algorithm is on track here, since it usually uses a so called union-find or disjoint-set datastructure for fast detection of cycles. This is the part of the Kruskals Algorithm page on wikipedia that you will need for your algorithm. This is also linked on wikipedia: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Answer 2

I found Kruskal's algorithm after long hours of research. I only needed to randomize the order in which I investigated the nodes of the graph.