Sprotni algoritmi za računanje razdelitve grafa na klikeFABIJAN, ALEKSANDER (Avtor) Brodnik, Andrej (Mentor) Nilsson, Bengt J. (Komentor) analiza konkurenčnostigrupiranjesprotni algoritemaproksimacijski algoritemGrupiranje v klike je proces združevanja vozlišč v gruče, za katere velja, da so vsa vozlišča med seboj povezana. V sprotnem (on-line) združevanju celoten graf ni znan vnaprej, ampak je na voljo po eno vozlišče naenkrat. Tista vozlišča, ki so že pridružena gruči, ne morejo biti prestavljena v drugo gručo. Naloga je poiskati takšno razvrstitev vozlišč, ki se od optimalne razvrstitve razlikuje čim manj. V tej diplomski nalogi podamo konstantno zgornjo mejo in algoritem (Lazy) za problem sprotnega združevanja v klike, kjer je cilj poiskati razvrstitev vozlišč s čim več povezavami znotraj gruč (problem Max-ECP). Poleg tega podamo ujemajoči zgornji in spodnji meji za problem sprotnega združevanja v klike, kjer je cilj poiskati razvrstitev s čim manj povezavami med gručami (problem Min-ECP). Za oba problema pokažemo, da naraven (Greedy) pristop vodi k linearni rešitvi. Naša metoda Lazy nudi konstantno tekmovalno razmerje, kar se znatno odraža na grafih z veliko vozlišči.20142014-09-04 11:15:01Diplomsko delo29432VisID: 13821sl