• DocumentCode
    3067099
  • Title

    A parallel algorithm for maximum independent set of a circular-arc graph

  • Author

    Sprague, Alan P.

  • Author_Institution
    Dept. of Comput. & Inf. Sci., Alabama Univ., Birmingham, AL, USA
  • fYear
    1992
  • fDate
    12-15 Apr 1992
  • Firstpage
    31
  • Abstract
    The author presents a parallel algorithm of cost O(n log n) to find a maximum independent set of a circular arc graph. In the CREW PRAM model the algorithm takes O(log n) time, while in the EREW PRAM model it requires O(log2 n) time. It illustrates the use of divide-and-conquer in parallel algorithms. The heart of the algorithm solves this problem on an interval graph, which is derived from the given circular arc graph. Postprocessing selects a maximum independent set on the given circular arc graph
  • Keywords
    graph theory; parallel algorithms; set theory; CREW PRAM model; EREW PRAM model; circular-arc graph; cost; divide-and-conquer; maximum independent set; parallel algorithm; postprocessing; Concurrent computing; Costs; Greedy algorithms; Heart; Parallel algorithms; Phase change random access memory; Polynomials; Zirconium;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Southeastcon '92, Proceedings., IEEE
  • Conference_Location
    Birmingham, AL
  • Print_ISBN
    0-7803-0494-2
  • Type

    conf

  • DOI
    10.1109/SECON.1992.202301
  • Filename
    202301
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3067099