Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time
| dc.creator | Kutz, Martin | |
| dc.date | 2005-12-15 | |
| dc.date.accessioned | 2026-07-07T06:53:51Z | |
| dc.date.available | 2026-07-07T06:53:51Z | |
| dc.description | We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded genus in O(n \log n) time, where n denotes the complexity of the surface. This solves a central open problem in computational topology, improving upon the current-best O(n^{3/2})-time algorithm by Cabello and Mohar (ESA 2005). Our algorithm uses universal-cover constructions to find short cycles and makes extensive use of existing tools from the field. | |
| dc.description | 13 pages, 7 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0512064 | |
| dc.identifier | http://arxiv.org/abs/cs/0512064 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105735 | |
| dc.subject | Computational Geometry | |
| dc.title | Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time | |
| dc.type | text |