跳到主要內容

臺灣博碩士論文加值系統

(100.28.132.102) 您好!臺灣時間:2024/06/16 15:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:劉奕志
研究生(外文):Yi-Chi Liu
論文名稱:最大有限分支度一集合問題之啟發式演算法與分支化約演算法研究
論文名稱(外文):Heuristics and a Promising Branch-and-Reduce Algorithm for the Maximum Bounded-Degree-1 Set Problem
指導教授:吳邦一張貿翔張貿翔引用關係
指導教授(外文):Bang-Ye WuMaw-Shang Chang
口試委員:張貿翔吳邦一李新林黃耀廷
口試委員(外文):Maw-Shang ChangBang-Ye WuSing-Ling LeeYao-Ting Huang
口試日期:2013-06-28
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:45
中文關鍵詞:分支化約演算法正確解演算法最大有限分支度一集合
外文關鍵詞:Branch-and-Reduce AlgorithmExact AlgorithmMax 1-BDS
相關次數:
  • 被引用被引用:0
  • 點閱點閱:236
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:1
有限分支度一集合問題 (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.
1 Introduction 1
1.1 Previous results . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 The main results . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Preliminaries 5
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 0/1 Integer Linear Programming of the Max 1-BDS problem 5

3 Heuristic algorithms and an exact algorithm 7
3.1 Reduction rules . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1 DROP . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 SELECT . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.3 IDROP . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.4 ISELECT . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Branch-and-reduce algorithms . . . . . . . . . . . . . . . . . 20
3.3.1 Discard rst . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.2 Select rst . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Experiment results 26

5 Concluding remarks 41

[1] B. Balasundaram, Cohesive subgroup model for graph-based text mining,
Proceedings of the 2008 IEEE Conference on Automation Science
and Engineering, pp. 989{994, 2008.
[2] B. Balasundaram, S. Chandramouli, and S. Trukhanov, Approximation
algorithms for nding and partitioning unit-disk graphs into co-k-
plexes, Optimization Letters, 4 (2010), pp. 311{320.
[3] B. Balasundaram, S. Butenko, and I. V. Hicks, Clique relaxations in
social network analysis: The maximum k-plex problem, Operations
Research 59 (2011), pp. 133{142.
[4] V. Batagelj and A. Mrvar, Pajek datasets.
http://vlado.fmf.uni-lj.si/pub/networks/data/
[5] V. Batagelj, Network/Pajek Graph Files.
http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm
[6] N. Betzler, R. Bredereck, R. Niedermeier, and J. Uhlmann, On
bounded-degree vertex deletion parameterized by treewidth, Discrete
Applied Mathematics, 160 (2012), pp. 53{60.
[7] R. van Bevern, H. Moser, and R. Niedermeier, Approximation and
tidying{a problem kernel for s-plex cluster vertex deletion, Algorith-
mica, 62 (2012), pp. 930{950.
[8] M.-S. Chang, L.-J. Hung, and P.-C. Su, Exact and xed-parameter
algorithms for problems related to 2-plex, Proceedings of ICSEC 2011,
pp. 203{208, 2011.
[9] M.-S. Chang, L.-J. Hung, P.-C. Su, Measure and conquer: analysis
of a branch-and-reduce algorithm for the maximum bounded-degree-
1 set problem, in proceedings of the 29th Workshop on Combinatorial
Mathematics and Computation Theory, pp. 136{145, 2012.
[10] M.-S. Chang and L.-J. Hung, Moderately exponential time approximation
algorithms for the maximum bounded-degree-1 set problem, in
Proceedints of the 30th Workshop on on Combinatorial Mathematics
and Computation Theory, pp. 23{30, 2013.
[11] DIMACS: Maximum clique, graph coloring, and satis ability,
Second DIMACS implementation challenge (1995),
http://dimacs.rutgers.edu/Challenges/.
[12] I. Dinur and S. Safra, The importance of being biased, Proceedings of
STOC 2002, pp. 33{42.
[13] M. R. Fellows, J. Guo, H. Moser, and R. Niedermeier, A generalization
of Nemhauser and Trotter's local optimization theorem, Journal of
Computer and System Sciences, 77 (2011), pp. 1141{1158.
[14] J. Guo, C. Komusiewicz, R. Niedermeier, and J. Uhlmann, A more
relaxed model for graph-based data clustering: s-plex cluster editing,
SIAM Journal on Discrete Mathematics, 24 (2010), pp. 1662{1683.
[15] J. Grossman, P. Ion, and R. de Castro, The Erd}os Number Project.
http://www.oakland.edu/enp
[16] C. Komusiewicz, F. Hu ner, H. Moser, and R. Niedermeier, Isolation
concepts for eciently enumerating dense subgraphs, Theoretical Com-
puter Science, 410 (2009), pp. 3640{3654.
[17] B. McClosky and I.V. Hicks, Combinatorial algorithms for the maximum
k-plex problem, Journal of Combinatorial Optimization, 23
(2012) pp. 29{49.
[18] H. Moser, R. Niedermeier, and M. Sorge, Exact combinatorial algorithms
and experiments for nding maximum k-plexes, Journal of
Combinatorial Optimization, 24 (2012), pp. 347{373.
[19] N. Nishmura, P. Ragde, and D. M. Thilikos, Fast xed-parameter
tractable algorithms for nontrivial generalizations of vertex cover, Dis-
crete Applied Mathematics, 152 (2005), pp. 229{245.
[20] S. B. Seidman and B. L. Foster, A graph-theoretic generalization of
the clique concept, The Journal of Mathematical Sociology 6 (1978),
pp. 139{154.
[21] S. Trukhannov, Novel approaches for solving large-scale optimization
problems on graphs, PhD Thesis, A&M University, Texas, 2008.
[22] B.Wu and X. Pei, A parallel algorithm for enumerating all the maximal
k-plexes, Proceedings of PAKDD 2007, LNAI 4819 (2007), pp. 476{483.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top