• DocumentCode
    2155509
  • Title

    An optimal parallel algorithm for graph planarity

  • Author

    Ramachandran, Vijaya ; Reif, John

  • Author_Institution
    Texas Univ., Austin, TX, USA
  • fYear
    1989
  • fDate
    30 Oct-1 Nov 1989
  • Firstpage
    282
  • Lastpage
    287
  • Abstract
    The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity
  • Keywords
    computational complexity; graph theory; parallel algorithms; random-access storage; CRCW PRAM; embedding; graph connectivity; graph planarity; open ear decomposition; optimal parallel algorithm; Concurrent computing; Contracts; Ear; NASA; Parallel algorithms; Phase change random access memory; Polynomials; Semiconductor device modeling; Testing; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1989., 30th Annual Symposium on
  • Conference_Location
    Research Triangle Park, NC
  • Print_ISBN
    0-8186-1982-1
  • Type

    conf

  • DOI
    10.1109/SFCS.1989.63491
  • Filename
    63491
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2155509