Combinatorial optimization of cycles and bases

Advances in Applied and Computational Topology (Afra Zomorodian, editor), pp. 195–228.
Proceedings of Symposia in Applied Mathematics 70, American Mathematical Society, 2012.
(Proceedings of the Short Course on Computational Topology at the 2011 Joint Mathematics Meetings)

• Download final version:
• Download slides from AMS short course:

Abstract:

We survey algorithms and hardness results for two important classes of topology optimization problems: computing minimum-weight cycles in a given homotopy or homology class, and computing minimum-weight cycle bases for the fundamental group or various homology groups.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 18 Jul 2012