• DocumentCode
    2189004
  • Title

    Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs

  • Author

    Galil, Zvi ; Galil, Zvi ; Galil, Zvi ; Galil, Zvi ; Micali, Silvio ; Micali, Silvio ; Micali, Silvio ; Micali, Silvio ; Gabow, Harold ; Gabow, Harold ; Gabow, Harold ; Gabow, Harold

  • fYear
    1982
  • fDate
    3-5 Nov. 1982
  • Firstpage
    255
  • Lastpage
    261
  • Abstract
    We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.
  • Keywords
    Computer science; Data structures; RNA;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1982. SFCS '08. 23rd Annual Symposium on
  • Conference_Location
    Chicago, IL, USA
  • ISSN
    0272-5428
  • Type

    conf

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