The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class $AC^1$. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to $UL \cap coUL$. As a consequence of our method we get that the isomorphism problem for oriented graphs is in $NL$. We also show that the problems are hard for $L$.

Keywords

Data Structures and Algorithms, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/155218

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.2825
 http://arxiv.org/abs/0802.2825
 Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)

Collections

arXiv