• DocumentCode
    3019353
  • Title

    An O(n½+?)-Space and Polynomial-Time Algorithm for Directed Planar Reachability

  • Author

    Imai, Tetsuro ; Nakagawa, Koichi ; Pavan, A. ; Vinodchandran, N.V. ; Watanabe, Osamu

  • Author_Institution
    Dept. of Math. & Comput. Sci., Tokyo Inst. of Technol., Tokyo, Japan
  • fYear
    2013
  • fDate
    5-7 June 2013
  • Firstpage
    277
  • Lastpage
    286
  • Abstract
    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).
  • Keywords
    computational complexity; directed graphs; reachability analysis; directed planar graphs; directed planar reachability; general directed graphs; polynomial-time algorithm; space algorithm; Algorithm design and analysis; Complexity theory; Face; Particle separators; Polynomials; Silicon; Standards; directed planar graph; polynomial time; reachability; sublinear space;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2013 IEEE Conference on
  • Conference_Location
    Stanford, CA
  • Type

    conf

  • DOI
    10.1109/CCC.2013.35
  • Filename
    6597770
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3019353