• DocumentCode
    2765461
  • Title

    A fast NC algorithm to recognize P4-reducible graphs

  • Author

    Lin, R. ; Olariu, S.

  • Author_Institution
    Dept. of Comput. Sci., State Univ. of New York, Geneseo, NY, USA
  • fYear
    1990
  • fDate
    22-25 Oct 1990
  • Firstpage
    402
  • Lastpage
    413
  • Abstract
    A parallel algorithm to recognize P4-reducible graphs and to construct their corresponding tree representation is presented. Terminology and background are given for P4-reducible graphs and the cographs of which they are a natural generalization. The algorithm runs in O(log n) time using O((n2+mn)/log n), where n is the number of vertices and m the number of edges, in the EREW PRAM model. Some open problems are stated
  • Keywords
    computational complexity; graph theory; EREW PRAM model; NC algorithm; P4-reducible graphs; cographs; edges; parallel algorithm; tree representation; Application software; Character recognition; Clustering algorithms; Computer science; Parallel algorithms; Parallel processing; Processor scheduling; Read-write memory; Scheduling algorithm; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Technology, 1990. 'Next Decade in Information Technology', Proceedings of the 5th Jerusalem Conference on (Cat. No.90TH0326-9)
  • Conference_Location
    Jerusalem
  • Print_ISBN
    0-8186-2078-1
  • Type

    conf

  • DOI
    10.1109/JCIT.1990.128311
  • Filename
    128311
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2765461