VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
Celotno besedilo
  • Pasovnost grafa in semidefinitno programiranje
    Povh, Janez, 1973-
    V članku je obravnavan probem pasovne širine grafa, ki je dokaj znan NP-težak problem. Jedro članka predstavlja aproksimacijski algoritem za približno reševanje tega problema, temelječ na ... semidefinitnem programiranju. Za ta algoritem je narejena tudi analiza kvalitete, ki pokaže, da je pričakovani rezultat soliden. Težava tega pristopa pa je v tem, da je število omejitev eksponentno. Metode notranjih točk tako niso uporabne, zaradi enostavne preverljivosti zahtev pa lahko uporabimo elipsoidno metodo ali metodo svežnjev, ki pa sta v praksi zelo počasni.
    Vir: Zbornik posvetovanja (str. 247-252)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2003
    Jezik - slovenski
    COBISS.SI-ID - 9705889