Information Technology Reference
In-Depth Information
[Poo93] C.K. Poon, in
Space Bounds for Graph Connectivity Problems on Node-Named Jags
and Node-Ordered Jags
(FOCS, 1993), pp. 218-227
[RA00] K. Reinhardt, E. Allender, Making nondeterminism unambiguous. SIAM J. Comput.
29
(4), 1118-1131 (2000)
[Rei08] O. Reingold, Undirected connectivity in log-space. J. ACM,
55
(4), 1-24 (2008)
[RTV06] O. Reingold, L. Trevisan, S. Vadhan, Pseudorandom walks on regular digraphs and
the RL versus L problem, in
STOC '06: Proceedings of the thirty-eighth annual ACM
Symposium on Theory of Computing
, (ACM, New York, NY, USA, 2006), pp. 457-466
[Sav70] W.J. Savitch, Relationships between nondeterministic and deterministic tape complex-
ities. J. Comput. Syst. Sci.
4
(2), 177-192 (1970)
[SBV10] D. Stolee, C. Bourke, N.V. Vinodchandran, A log-space algorithm for reachability in
planar dags with few sources, in
Proceedings of 25th IEEE Conference on Computa-
tional Complexity
(2010), pp. 131-138
[SV12] D. Stolee, N.V. Vinodchandran. Space-efficient algorithms for reachabilityin surface-
embedded graphs, in
IEEE Conference on Computational Complexity
(2012), pp. 326-
333
[Sze88] R. Szelepcsényi, The method of forced enumeration for nondeterministic automata.
Acta Informatica
26
, 279-284 (1988)
[TV12] R. Tewari, N.V. Vinodchandran, Green's theorem and isolation in planar graphs. Inf.
Comput.
215
, 1-7 (2012)
[TW09] T. Thierauf, F. Wagner, in
Reachability in K
3,3
-free graphs and K
5
-free graphs is in
unambiguous log-space
(FCT, 2009), pp. 323-334
[Wig92] A. Wigderson, The complexity of graph connectivity. Math. Found. Comput. Sci.
1992
,
112-132 (1992)
[Wig94] A. Wigderson. NL/poly
L/poly. In Proceedings of the 9th Structures in Complexity
conference, pages 59-62, 1994
ₔ∀
