Event Type:

Geometry-Topology Seminar

Date/Time:

Monday, November 17, 2014 - 12:00 to 13:00

Location:

Gilkey Hall 115

Guest Speaker:

Institution:

Oregon State University

Abstract:

Intuitively, homology is a tool for studying different dimensional holes of

a topological space. The homology of one-dimensional cycles in surfaces

have been studied for their applications in computer science, and several

algorithms have been proposed to compute with them. The first step of many

of these algorithms is computing a basis of the homology group.

In this talk, we consider the problem of finding a shortest basis for the

homology group of an orientable surface. We briefly discuss its relation

with the well-known minimum cycle basis problem from graph theory. Then,

we mention a couple of old methods to compute the shortest homology basis.

Finally, we present a recent nearly linear time algorithm for this problem.

This is a joint work with Erin Chambers and Kyle Fox.