文章基本信息

标题：Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space
本地全文：下载
作者：Fabian Wagner ; Thomas Thierauf
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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, UL \cap coUL. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in UL \cap coUL. 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 reachabilty properties. For K_5-free graphs we also need a decomposition into fourconnected components. A careful analysis finally gives a polynomial size planar graph which can be computed in log-space. 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.
关键词：3}-free , Distance , K_5-free , K_{3 , Long-Path , reachability , Unambiguous Log-space