• DocumentCode
    3262050
  • Title

    On the parallel recognition of some tree-representable graphs

  • Author

    Lin, R. ; Olariu, S.

  • Author_Institution
    Dept. of Comput. Sci., State Univ. of New York, Geneseo, NY, USA
  • fYear
    1990
  • fDate
    9-13 Dec 1990
  • Firstpage
    6
  • Lastpage
    13
  • Abstract
    The authors present a fast parallel recognition algorithm for a class of tree-representable graphs and show how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation. With a graph G=(V,E) with |V|=n and |E|=m as input, the algorithms run in O(log n) time using O((n2 +mn)/log n) processors in the EREW-PRAM model
  • Keywords
    computational complexity; graph theory; parallel algorithms; trees (mathematics); EREW-PRAM model; data structures; parallel recognition algorithm; tree-representable graphs; Character recognition; Clustering algorithms; Terminology; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
  • Conference_Location
    Dallas, TX
  • Print_ISBN
    0-8186-2087-0
  • Type

    conf

  • DOI
    10.1109/SPDP.1990.143498
  • Filename
    143498
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3262050