Department of Mathematics and Statistics, SFU
Wednesday, 11 March 1998, 3:30pm

COLLOQUIUM

Visualization of Combinatorial Algorithms

Luis Goddyn
(604) 291-4699
K9509 (SFU)
CECM

Abstract:
We explore several combinatorial optimization problems
using software developed by myself and Mike Maguire.
We gain a "visual" knowlege of the meaning of key
concepts such as complementary slackness and 
performance guarantees through graphics-based
implementations of the standard primal-dual algorithms
for perfect matchings, edge covers, spanning trees and
network flows.   For example we shall see for example
the simplest proof that I know that the greedy algorithm
always produces a minimum cost spanning tree