부산대학교 도서관

Summary: ``We show that the reachability problem for directed graphs that are either $K_{3,3}$-free or $K_5$-free is in unambiguous log-space, $\ssf{UL}\cap\ssf{coUL}$. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in $\ssf{UL}\cap\ssf{coUL}$. \par ``Our algorithm decomposes the graphs into biconnected and triconnected components. This gives a tree structure on these components. The non-planar components are replaced by planar components that maintain the reachability properties. For $K_5$-free graphs we also need a decomposition into 4-connected components. Thereby we provide a logspace 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 longest paths in $K_{3,3}$-free and $K_5$-free directed acyclic graphs.''