CATBox - An Interactive Course in Combinatorial
Optimization
by W. Hochstaettler and A. Schliep
2010, published by Springer
ISBN: 978-3-540-14887-6
http://www.springer.com/978-3-540-14887-6
About this book:
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 correctness 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
combinatorial 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/.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
