• DocumentCode
    3151827
  • Title

    A sublinear space, polynomial time algorithm for directed s-t connectivity

  • Author

    Barnes, Greg ; Buss, Jonathan F. ; Ruzzo, Walter L. ; Schieber, Baruch

  • Author_Institution
    Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    27
  • Lastpage
    33
  • Abstract
    A deterministic sublinear space, polynomial-time algorithm for directed s-t connectivity, which is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph, is presented. For n-vertex graphs, the algorithm can use as little as n/2Θ(√log n) space while still running in polynomial time
  • Keywords
    computational complexity; directed graphs; deterministic sublinear space algorithm; directed graph; directed s-t connectivity; polynomial time algorithm; vertex path; Computational complexity; Computational modeling; Computer science; Degradation; Marine vehicles; Polynomials; Prototypes; Turing machines; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
  • Conference_Location
    Boston, MA
  • Print_ISBN
    0-8186-2955-X
  • Type

    conf

  • DOI
    10.1109/SCT.1992.215378
  • Filename
    215378
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3151827