藉由實驗的方式研究圖論上邊修改問題

An Experimental Study of Cluster Editing Problems

王俊杰(Chun-Chieh Wang)

指導教授 ： 吳邦一

國立中正大學/工學院/資訊工程學系/碩士(2013年)

摘要

HASH(0x210fc5e0)

關鍵字

分群 ； 分支定界法 ； 演算法 ； 近似演算法

並列摘要

A cluster graph is an undirected graph composed of disjoint maximal cliques. In this thesis, we study the problem Min-Max Cluster Editing which minimizes the maximum number of inserting and deleting edges incident to any vertex. We design a 2-approximation algorithm and show a polynomial-time solvable case. We also present a branching algorithm for solving the problem exactly. Another problem is a variant of p-Correlation Clustering named p-Correlation Clustering for Labelled Items (p-CCLI). For this problem, each vertex is given one or more label indicating the cluster it can be clustered into. For p-CCLI, we design some reduction rules and present a tree-search algorithm. By experiments on random graphs, we show the performance of our algorithms.

並列關鍵字

clustering ； branch-and-bound ； algorithm ； approximation algorithm

參考文獻

[1] N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and clustering, J. ACM 55(5):1–27, 2008.

[3] S. B¨ocker, A golden ratio parameterized algorithm for cluster editing, Journal of Discrete Algorithms, 2012.

[4] S. B¨ocker and P. Damaschke, Even faster parameterized cluster deletion and cluster editing, Inf. Process. Lett. 111(14):717–721, 2011.

[5] S. B¨ocker, S. Briesemeister, Q.B.A. Bui, A. Truss, Going weighted: Parameterized algorithm for cluster editing, Theor. Comput. Sci. 410

(52):5467–5480, 2009.