Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Kutz, Martin

dblp



Editor(s):

Amenta, Nina
Cheong, Otfried

dblp
dblp

Not MPII Editor(s):

Amenta, Nina
Cheong, Otfried

BibTeX cite key*:

Kutz2006

Title, Booktitle

Title*:

Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time.

Booktitle*:

Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06

Event, URLs

URL of the conference:

http://socg06.cs.arizona.edu/

URL for downloading the paper:


Event Address*:

Sedona, Arizona, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

5 June 2006

Event End Date:

7 June 2006

Publisher

Name*:

ACM

URL:

http://www.acm.org/

Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

430-437

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

1-59593-340-9

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

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 \frac{3}{2})$-time algorithm by Cabello and Mohar (ESA 2005).
Our algorithm is based on universal-cover constructions to find short cycles and makes extensive use of existing tools from the field.

Keywords:

computational topology, non-trivial cycles, efficient algorithm, planar graph, system of loops, universal cover



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kutz2006,
AUTHOR = {Kutz, Martin},
EDITOR = {Amenta, Nina and Cheong, Otfried},
TITLE = {Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time.},
BOOKTITLE = {Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06},
PUBLISHER = {ACM},
YEAR = {2006},
PAGES = {430--437},
ADDRESS = {Sedona, Arizona, USA},
ISBN = {1-59593-340-9},
}


Entry last modified by Regina Kraemer, 04/16/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Pascal Schweitzer
Created
02/28/2007 01:03:49 PM
Revisions
3.
2.
1.
0.
Editor(s)
Regina Kraemer
Christine Kiesel
Pascal Schweitzer
Pascal Schweitzer
Edit Dates
04/16/2007 09:56:47 AM
12.03.2007 08:00:47
02/28/2007 01:06:52 PM
02/28/2007 01:03:49 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section