Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UNAMBIGUOUS LOGSPACE:
Reports tagged with unambiguous logspace:
TR07-068 | 24th July 2007
Thomas Thierauf, Fabian Wagner

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

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

TR10-009 | 13th January 2010
A. Pavan, Raghunath Tewari, N. V. Vinodchandran

#### On the Power of Unambiguity in Logspace

We report progress on the \NL\ vs \UL\ problem.
\begin{itemize}
\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.
\item[-] We investigate the complexity of min-uniqueness - a central
notion in studying the \NL\ vs \UL\ problem.
more >>>

TR10-201 | 21st December 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari

#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in ... more >>>

TR19-039 | 12th March 2019
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee