부산대학교 도서관

Summary: ``We show that the reachability problem for directed graphsthat are either $K_{3,3}$-free or $K_5$-free is in unambiguouslog-space, $\ssf{UL}\cap\ssf{coUL}$. This significantly extends theresult of Bourke, Tewari, and Vinodchandran that the reachabilityproblem for directed planar graphs is in $\ssf{UL}\cap\ssf{coUL}$.\par``Our algorithm decomposes the graphs into biconnected and triconnectedcomponents. This gives a tree structure on these components. Thenon-planar components are replaced by planar components that maintainthe reachability properties. For $K_5$-free graphs we also need adecomposition into 4-connected components. Thereby we provide alogspace reduction to the planar reachability problem.\par``We show the same upper bound for computing distances in$K_{3,3}$-free and $K_5$-free directed graphs and for computing longestpaths in $K_{3,3}$-free and $K_5$-free directed acyclic graphs.''