An <i>O</i>(<i>n</i>^1/2+ε)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

スポンサーリンク

概要

• 論文の詳細を見る

• We show that the reachability problem over directed planar graphs can be solved simultaneously in polynomial time and approximately O(√n) space. In contrast, the best space bound known for the reachability problem on general directed graphs with polynomial running time is O(n/2√log n).

• 2013-05-10

著者

• Osamu Watanabe

  Dept. of Math. and Computer Science, Tokyo Inst. of Technology

• Tatsuya Imai

  Dept. of Math. and Computer Science, Tokyo Inst. of Technology

• Kotaro Nakagawa

  Dept. of Math. and Computer Science, Tokyo Inst. of Technology

関連論文

• An O(n1/2+ε)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

スポンサーリンク