NUK - logo
Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • A parallel algorithm for computing the critical independence number and related sets
    DeLaViña, Ermelinda ; Larson, Craig Erik
    An independent set ▫$I_c$▫ is a critical independent set if ▫$|I_c| - |N(I_c)| \ge |J| - |N(J)|$▫, for any independent set ▫$J$▫. The critical independence number of a graph is the cardinality of a ... maximum critical independent set. This number is a lower bound for the independence number and can be computed in polynomial-time. The existing algorithm runs in ▫${\mathcal O}\left( n^{2.5}\sqrt{(m/\log n}\right)$▫ time for a graph ▫$G$▫ with ▫$n = |V(G)|$▫ vertices and ▫$m$▫ edges. It is demonstrated here that there is a parallel algorithm using ▫$n$▫ processors that runs in ▫${\mathcal O}\left( n^{1.5} \sqrt{(m/\log n}\right)$▫ time. The new algorithm returns the union of all maximum critical independent sets. The graph induced on this set is a König-Egerváry graph whose components are either isolated vertices or which have perfect matchings.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 6, no. 2, 2013, str. 237-245)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 16473945

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/view/165/213
    Digitalna knjižnica Slovenije - dLib.si

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 6, no. 2, 2013, str. 237-245)

loading ...
loading ...
loading ...

Vnos na polico