論文

査読有り
2014年

(O)over-tilde(root n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE, PT II
  • Tetsuo Asano
  • ,
  • David Kirkpatrick
  • ,
  • Kotaro Nakagawa
  • ,
  • Osamu Watanabe

8635
開始ページ
45
終了ページ
56
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
出版者・発行元
SPRINGER-VERLAG BERLIN

The directed graph reachability problem takes as input an n-vertex directed graph G = (V, E), and two distinguished vertices v(0), and vertex v*. The problem is to determine whether there exists a path from v(0) to v* in G. The main result of this paper is to show that the directed graph reachability problem restricted to planar graphs can be solved in polynomial time using only (O) over tilde (root n) space(1).

Web of Science ® 被引用回数 : 3

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000358254600005&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000358254600005

エクスポート
BibTeX RIS