Greedy optimal homotopy and homology generators

Jeff Erickson, Kim Whittlesey

Research output: Contribution to conferencePaperpeer-review


We describe simple greedy algorithms to construct the shortest set of loops that generates either the fundamental group (with a given basepoint) or the first homology group (over any fixed coefficient field) of any oriented 2-manifold. In particular, we show that the shortest set of loops that generate the fundamental group of any oriented combinatorial 2-manifold, with any given basepoint, can be constructed in O(n log n) time using a straightforward application of Dijkstra's shortest path algorithm. This solves an open problem of Colin de Verdière and Lazarus.

Original languageEnglish (US)
Number of pages9
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Greedy optimal homotopy and homology generators'. Together they form a unique fingerprint.

Cite this