izpis_h1_title_alt

Sprotni algoritmi za računanje razdelitve grafa na klike
FABIJAN, ALEKSANDER (Avtor), Brodnik, Andrej (Mentor) Več o mentorju... Povezava se odpre v novem oknu, Nilsson, Bengt J. (Komentor)

.pdfPDF - Predstavitvena datoteka, prenos (616,97 KB)
MD5: 60B21CC102D76AFCBFC98965D37FB35B

Izvleček
Grupiranje 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.

Jezik:Angleški jezik
Ključne besede:analiza konkurenčnosti, grupiranje, sprotni algoritem, aproksimacijski algoritem
Vrsta gradiva:Diplomsko delo (m5)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2014
Število ogledov:1001
Število prenosov:357
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Online Algorithms for Graph Partitioning into Cliques
Izvleček:
Clique clustering is the problem of partitioning a graph into cliques so that some objective function is optimised. In online clustering the input graph is given one vertex at a time, and vertices that have been previously clustered are not allowed to be separated. The objective is to maintain a clustering that never deviates too far from the optimal offline solution. We give a constant competitive upper bound and a strategy (Lazy) for online clique clustering, where the objective function is to maximise the number of edges inside the clusters (Max-ECP). We also give almost matching upper and lower bounds on the competitive ratio for online clique clustering, where we want to minimise the number of edges between clusters (Min-ECP). In addition, we prove that the greedy method only gives linear competitive ratio for these problems. The research result shows that the proposed constant competitive strategy performs significantly better on bigger graphs than the greedy method.

Ključne besede:competitive analysis, clustering, online algorithm, approximation algorithm

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj