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

Authors Thomas Thierauf, Fabian Wagner



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1327.pdf
  • Filesize: 168 kB
  • 12 pages

Document Identifiers

Author Details

Thomas Thierauf
Fabian Wagner

Cite AsGet BibTex

Thomas Thierauf and Fabian Wagner. The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 633-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1327

Abstract

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$.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail