Open Research Newcastle
Browse

2-manifold recognition is in logspace

Download (366.16 kB)
journal contribution
posted on 2025-05-09, 12:05 authored by Benjamin A. Burton, Murray Elder, Arkadius Kalka, Stephen Tillmann
We prove that the homeomorphism problem for 2-manifolds can be decided in logspace. The proof relies on Reingold's logspace solution to the undirected s,t-connectivity problem in graphs.

Funding

ARC

DP110101104

History

Related Materials

  1. 1.
    DOI - Is published in https://doi.org/10.20382/jocg.v7i1a4
  2. 2.
    ISSN - Is version of https://portal.issn.org/resource/ISSN/1920-180X

Journal title

Journal of Computational Geometry

Volume

7

Issue

1

Pagination

70-85

Publisher

Carleton University, Department of Mathematics and Statistics

Language

  • en, English

College/Research Centre

Faculty of Science and Information Technology

School

School of Mathematical and Physical Sciences

Usage metrics

    Publications

    Categories

    Keywords

    2-manifoldslogspaceReingold's logspace solution

    Licence

    CC BY 3.0

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC