CATBox: An Interactive Course in Combinatorial Optimization

✍ Scribed by Winfried Hochstättler

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 195
• Category: Library

✦ Synopsis

Graph algorithms are easy to visualize and indeed there already exists a variety of packages to animate the dynamics when solving problems from graph theory. Still 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. In the course book, intended for readers at advanced undergraduate or graduate level, 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, weighted and unweighted matchings both for bipartite and non-bipartite graphs.

Find more information at http://schliep.org/CATBox/.

✦ Table of Contents

CATBox
Preface
Contents
to 1 Discrete Problems from Applications
to 2 Basics, Notation and Data Structures
Definition of a Graph
How to Represent a Graph on the Computer?
Basic Terminology from Graph Theory
Algorithms and Complexity
Correctness
Running Time
Two Graph Traversals
to 3 Minimum Spanning Trees
Minimum Connected Subgraphs
Trees
Minimum Spanning Trees
Kruskal's Algorithm
Prim's Algorithm
Remarks
Some Additional Notation
to 4 Linear Programming Duality
The MST-Polytope
Farkas' Lemma
Duality Theorem of Linear Programming
The Greedy as Primal-Dual Algorithm
The Base Polytope
to 5 Shortest Paths
Introduction
Dijkstra's Algorithm
Some Considerations about Implementations
Special Label Setting Methods for the Computation of Shortest Paths Between Two Vertices
Label Setting Versus Label Correcting
Detecting Negative Circuits
Application
An Analog Computer and LP Duality
to 6 Maximal Flows
Introduction
The Algorithm of Ford and Fulkerson
Max-Flow-Min-Cut
Pathologies
Edmonds-Karp Implementation
Max-flow-Min-cut as Linear Programming Duality
Preflow Push
Preflow Push Considered as a Dual Algorithm
FIFO-Implementation
to 7 Minimum-Cost Flows
Introduction
Optimality Criteria
First Algorithms
Canceling Negative Circuits, the Primal Method
Augmenting Shortest Paths, the Dual Method
The Primal Dual Method
Polynomial Time Algorithms
Min Mean Circuit Canceling
Capacity Rounding
Cost Scaling
to 8 Matching
Bipartite Matching
Augmenting Paths
Non-Bipartite Graphs
The Tutte-Berge Formula
to 9 Weighted Matching
Bipartite Weighted Matching
Inverse Minimum Spanning Tree Problem
Non-Bipartite Matching
The Matching Polytope
The Weighted Matching Algorithm
Karyotyping and the Chinese Postman Problem
to A Using Gato and Gred
Easy Installation
Installing from Source
The Gato Application
Running Algorithms in Gato
Gred
Editing Graphs with Gred
to B A Brief Introduction to Reading Python
Where to Obtain Python
to C Visualizing Graph Algorithms with Gato
Interesting Events During Runtime
Rule-Based Visualization
Animated Data Structures (ADS)
Case Study: Ford-Fulkerson Algorithm
Implementation of Gato
ADS Defined in Gato
References
Index