Evaluation of permanents in rings and semirings

Andreas Björklund, Thore Husfeldt, Petter Kaski, Mikko Koivisto

    Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

    Abstract

    A study was conducted to present simple folklore algorithms to evaluate the permanent of a given matrix. Bellman-Held-Karp type dynamic programming was applied across column subsets in arbitrary semirings and showed that a transposed variant was considerably faster in commutative semirings. The starting point in arbitrary rings was Ryser's classic algorithm that was managed to expedite for rectangular matrices, remaining as the fastest known algorithm for square matrices. The time requirement of an algorithm was taken as the number of additions and multiplications it performed, to state the complexity bounds for each of the four cases. The space requirement was taken as the maximum number of semiring elements needed to keep in memory at any point in the computation. The study also discussed the role of commutativity where the first theorem suggested that commutativity was crucial for efficient evaluation of permanents.
    OriginalsprogEngelsk
    TidsskriftInformation Processing Letters
    Vol/bind110
    Sider (fra-til)867–870
    ISSN0020-0190
    DOI
    StatusUdgivet - 2010

    Emneord

    • Algorithms
    • Parameterized computation
    • Permanent

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Evaluation of permanents in rings and semirings'. Sammen danner de et unikt fingeraftryk.

    Citationsformater