Akademska digitalna zbirka SLovenije - logo
(UL)
  • Učinkovitost algoritmov za iskanje največje neodvisne množice vozlišč v grafih [Elektronski vir]
    Škerlep, Matej
    Problem največje neodvisne množice vozlišč je zanimiv problem iz teorije grafov, z izjemno uporabno vrednostjo pri določanju zaporedja v molekulah deoksiribonukleinskih kislin. V članku je za ... izhodišče vzeta formulacija problema v obliki celoštevilskega linearnega programa, ki je nato primerjan s svojo relaksacijo in algoritmom za lokalno iskanje na grafu. Primerjava je narejena na podlagi dobljenih množic vozlišč, ki jih algoritmi vračajo, in na podlagi časovne zahtevnosti posameznega algoritma. Analize so izvedene na naključnih grafih z do 100 vozlišči pri različnih verjetnostih povezave med dvema vozliščema. Za analizo časovne zahtevnosti je število vozlišč grafov povečevano do 2401. Na koncu je narejena še analiza na Petersenovem grafu in n-dimenzionalnih hiperkockah za 1 ▫$\leq$▫ n ▫$\leq$▫ 12. Na slednjih se za učinkovito izkaže tudi relaksacija celoštevilskega linearnega programa, kar omogoča ustrezno primerjavo časovne zahtevnosti vseh treh algoritmov.
    Vir: Matrika [Elektronski vir] : izbrane teme sodobne fizike in matematike. - ISSN 2385-8567 (Letn. 8, št. 1, 2021, 11 str.)
    Vrsta gradiva - e-članek ; neleposlovje za odrasle
    Leto - 2021
    Jezik - slovenski
    COBISS.SI-ID - 58802435

    Povezava(-e):

    http://matrika.fmf.uni-lj.si/letnik-8/stevilka-1/skerlep_m.pdf

Vnos na polico