• DocumentCode
    3204296
  • Title

    A near-optimal parallel algorithm for edge-coloring outerplanar graphs

  • Author

    Caspi, Yuval ; Dekel, Eliezer

  • Author_Institution
    Comput. Sci. Program, Texas Univ., Dallas, Richardson, TX, USA
  • fYear
    1992
  • fDate
    23-26 Mar 1992
  • Firstpage
    262
  • Lastpage
    266
  • Abstract
    The article presents a parallel EREW PRAM algorithm that runs in O(log2n) time using n/logn processors to optimally color the edges of an outerplanar graph. The algorithm improves the best known algorithm in both time, and number of processors. This more efficient algorithm is a result of a new approach for solving the problem. Also presented is a parallel EREW PRAM algorithm that runs in O(logn) using n/logn processors for finding a maximal matching in outerplanar graphs
  • Keywords
    computational complexity; graph colouring; parallel algorithms; edge-coloring; maximal matching; outerplanar graphs; parallel EREW PRAM algorithm; Color; Computational modeling; Computer science; Concurrent computing; Parallel algorithms; Phase change random access memory; Polynomials; Read-write memory; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1992. Proceedings., Sixth International
  • Conference_Location
    Beverly Hills, CA
  • Print_ISBN
    0-8186-2672-0
  • Type

    conf

  • DOI
    10.1109/IPPS.1992.223035
  • Filename
    223035
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3204296