最大有限分支度一集合問題之啟發式演算法與分支化約演算法研究

Heuristics and a Promising Branch-and-Reduce Algorithm for the Maximum Bounded-Degree-1 Set Problem

劉奕志(Yi-Chi Liu)

指導教授 ： 張貿翔 ； 吳邦一

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

摘要

有限分支度一集合問題 (1-BDS) ，是指在一張無向圖 G 中找出一個子集合 S，使得 S 在 G 中的誘導子圖 (induced subgraph) 每個點最多只會有一個鄰居，在圖中找出一組點數最多的有限分支度一集合，就是最大有限分支度一集合問題 (Max 1-BDS)

我們針對此問題提出一個新的簡單的分支約化演算法跟幾個啟發式演算法，並且認為會比前人使用較複雜的演算法更好。

從實驗數據中顯示，啟發式演算法可以找到很好的解，而且分支約化演算法在許多例子中比 Moser 等人的實驗結果比較有效率。

關鍵字

最大有限分支度一集合 ； 正確解演算法 ； 分支化約演算法

並列摘要

Given a graph G = (V, E), a bounded-degree-1 set S is a vertex subset of G such that the maximum degree in G[S] is at most one. The Maximum Bounded-Degree-1 Set "Max 1-bds" problem is to find a bounded-degree-1 set S of maximum cardinality in G.

It is an NP-hard problem and can not be approximated to a ratio greater than n^{e-1} in polynomial time for all e > 0 unless P = NP.
In this thesis, we design and implement heuristic algorithms and branch-and-reduce algorithms based on variant strategies.

Our the branch-and-reduce algorithms apply a very simple branching rule. From the experiment results, we observe that our heuristic algorithms find solutions with good qualities, and our branch-and-reduce algorithms are more efficient than the algorithm given by Moser et al. in most of test instances.

並列關鍵字

Exact Algorithm ； Branch-and-Reduce Algorithm ； Max 1-BDS

參考文獻

[1] B. Balasundaram, Cohesive subgroup model for graph-based text mining,

Proceedings of the 2008 IEEE Conference on Automation Science

algorithms for nding and partitioning unit-disk graphs into co-k-

social network analysis: The maximum k-plex problem, Operations

[5] V. Batagelj, Network/Pajek Graph Files.