## CATBox – An Interactive Course in Combinatorial Optimization

**W. Hochstättler and A. Schliep**

*
**Springer*, 2010.

Graph algorithms are easy to visualize and indeed there already exists a variety
of packages and programs to animate the dynamics when solving problems from
graph theory. Still, and somewhat surprisingly, it can be difficult to understand
the ideas behind the algorithm from the dynamic display alone.
CATBox consists of a software system for animating graph algorithms and a course
book which we developed simultaneously. The software system presents both the
algorithm and the graph and puts the user always in control of the actual code that
is executed. He or she can set breakpoints, proceed in single steps and trace into
subroutines. The graph, and additional auxiliary graphs like residual networks, are
displayed and provide visual feedback. The course book, intended for readers at
advanced undergraduate or graduate level, introduces the ideas and discusses the
mathematical background necessary for understanding and verifying the correct-
ness of the algorithms and their complexity. Computer exercises and examples
replace the usual static pictures of algorithm dynamics.
For this volume we have chosen solely algorithms for classical problems from combi-
natorial optimization, such as minimum spanning trees, shortest paths, maximum
flows, minimum cost flows as well as weighted and unweighted matchings both for
bipartite and non-bipartite graphs.
We consider non-bipartite weighted matching, in particular in the geometrical case,
a highlight of combinatorial optimization. In order to enable the reader to fully
enjoy the beauty of the primal-dual solution algorithm for weighted matching,
we present all mathematical material not only from the point of view of graph
theory, but also with an emphasis on linear programming and its duality. This yields
insightful and aesthetically pleasing pictures for matchings, but also for minimum
spanning trees.
You can find more information at http://schliep.org/CATBox/

Presented
on Nov. 24, 2000 by Alexander Schliep at Multimedia Tools for Communicating Mathematics, Lissabon, Portugal (Invited Talk).