#
Visual Matching

This is a port of some educational software I wrote several
years ago for Prof. Luis Goddyn of the Centre for Experimental and Constructive
Mathematics, Simon Fraser University. I haven't yet implemented
all the user-friendliness, animation and algorithms of the Macintosh C
versions, but the applet demonstrates some potential for Java's
use in visualization.

Here is a some further information (PDF)
on how the algorithm works.

For the **minimum weight non-bipartite perfect matching**, the colours don't matter --
just enter some points, then hit
step or go, and watch as the Java applet matches them up into pairs
using the minimum total line length.

For the **minimum weight bipartite perfect matching**, enter the same
number of red and blue points in the area provided below, watching as the Java applet finds the best way to marry all
the blue points to the red points using the minimum total line length.

For the **minimum weight spanning tree**, the colours don't matter --
just enter some points and watch the Java applet connect them up into a
network using the minimum total line length.

The ** minimum weight bipartite vertex cover ** algorithm is
not working correctly yet.... :-(

The algorithms are based on some work in *Geometric Duality and
Combinatorial Optimization* by M. Juenger, Universitaet zu Koeln and
W.R. Pulleyblank, IBM T. J. Watson Research Center.

Note: This applet was compiled with Sun's JDK version 1.02.

Michael
Maguire
Luis Goddyn

12
June 97