2-manifold recognition is in logspace

Burton, BA; Elder, M; Kalka, A; Tillmann, S

2-manifold recognition is in logspace

Burton, BA Elder, M

Kalka, A Tillmann, S

Permalink

Publication Type:: Journal Article

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (366.16 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Burton, BA	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Kalka, A	en_US
dc.contributor.author	Tillmann, S	en_US
dc.identifier.uri	http://hdl.handle.net/10453/97310
dc.description.abstract	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.	en_US
dc.title	2-manifold recognition is in logspace	en_US
dc.type	Journal Article
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access

Abstract:

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/97310