VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • A copositive programming approach to graph partitioning
    Povh, Janez, 1973- ; Rendl, Franz
    V članku obravnavamo problem delitve točk grafa na tri množice ▫$S_1$▫, ▫$S_2$▫ in ▫$S_3$▫ s predpisano močjo, tako da je skupna teža vseh povezav med ▫$S_1$▫ in ▫$S_2$▫ minimalna. Problem je tesno ... povezan z nekaterimi NP-težkimi problemi kot so npr. iskanje pasovne širine grafa in iskanje ločilca točk grafa. V članku pokažemo, da lahko ta problem zapišemo kot linearen program nad stožcem popolnoma pozitivnih matrik, kar nakaže naravno pot do semidefinitnih poenostavitev problema. Pokažemo tudi, da lahko spektralno poenostavitev, ki so jo predstavili Helmberg et al. (1995), zapišemo ekvivalentno kot semidefinitni program. Predlagamo tudi strožjo različico tega semidefinitnega programa in pokažemo na manjših grafih, da s tem dobimo bistveno boljšo spodnjo mejo od tiste, ki temelji na spektralni poenostavitvi.
    Vir: SIAM journal on optimization. - ISSN 1052-6234 (Vol. 18, no. 1, 2007, str. 223-241)
    Vrsta gradiva - članek, sestavni del
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 14289497

    Povezava(-e):

    http://dx.doi.org/10.1137/050637467

vir: SIAM journal on optimization. - ISSN 1052-6234 (Vol. 18, no. 1, 2007, str. 223-241)
loading ...
loading ...
loading ...

Vnos na polico