最大平衡子圖之演算法

Algorithms for the Maximum Balanced Subgraph Problem

林欣漢(Hsin-Han Lin)

指導教授 ： 吳邦一

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

摘要

令G=(V,E)為一個無向有號圖，它的邊可以被標記為'+'或'-'其中一個記號。一個平衡圖定義為圖裡面所有cycle的負邊數量皆為偶數。在此篇論文中，我們要研究的是最大平衡子圖問題，目的是要找一個最大的邊子集F使得F構成的子圖為平衡圖。我們針對一些有條件限制的圖和平面圖去找出多項式時間的演算法；對於一般的圖我們有2倍近似演算法和分支定界演算法。實驗部分使用隨機圖去測量，結果顯示出分支定界演算法優於天然的演算法。

關鍵字

平面圖 ； 平衡圖 ； 社會網路 ； 演算法

並列摘要

Let G=(V,E) be an undirected signed graph whose edge is marked a sign: either positive sign '+' or negative sign '-'. A signed graph is balanced if every cycle has even number of negative edges. In this paper, we study the maximum balanced subgraph problem, whose goal is to find a maximum subset F of edges such that the subgraph induced by F is balanced. We present polynomial-time algorithms for graphs with a special constraint and for planar graphs, a 2-approximation algorithm, and a branch-and-bound algorithm for general graphs. By experiments on random graphs, we show that our branch-and-bound algorithm is much faster than a trivial one.

並列關鍵字

planar graph ； balanced graph ； social network ； algorithm

參考文獻

[1] A. Avidor, M. Langberg, The multi-multiway cut problem, Proceedings

the Machine Learning, Special Issue on Clustering, Volume 56: pp. 89{

[3] C. Chiang, A. B. Kahng, S. Sinha, X. Xu, A. Z. Zelikovsky, Fast and

Transactions on Computer-Aided Design of Integrated Circuits and Sys-

tems, Volume 26(1): pp. 115{126, 2007.