An O(n^<1/2+E>)-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

著者

• Watanabe Osamu

  Dept. Computer Science Tokyo Institute Of Technology

• NAKAGAWA Kotaro

  Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology

• IMAI TATSUYA

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

• VINODCHANDRAN N.V.

  Dept. of Comp. Sci. & Eng., Univ. of Nebraska-Lincoln

• PAVAN A.

  Dept. of Computer Science, Iowa State University

• NAKAGAWA KOTARO

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

• VINODCHANDRAN N.V.

  Dept. of Comp. Sci. & Eng., Univ. of Nebraska-Lincoln

関連論文

• Pseudo Expectation : A Tool for Analyzing Local Search Algorithms
• DS-1-7 On Coppersmith's Technique and its Limit
• On Polynomial Time Many-One Completeness of One-Way Functions : Preliminary Report
• Spectral Analysis of Random Sparse Matrices
• The Relation between Time and Accepting Probability on Probabilistic Simple Decision Trees : Extended abstract(Mathematical Theories on Computing Schemes and Their Applications)
• A planted solution model for the MAX-2SAT problem (情報物理学の数学的構造--RIMS研究集会報告集)
• DS-1-6 A Message Passing Algorithm for MAX2SAT
• The First Eigenvalue of (c,d)-Regular Graph
• An O(n^)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

スポンサーリンク