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

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

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC