# 臺灣博碩士論文加值系統

(100.28.132.102) 您好！臺灣時間：2024/06/16 15:23

:::

### 詳目顯示

:

• 被引用: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 11.1 Previous results . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 The main results . . . . . . . . . . . . . . . . . . . . . . . . 42 Preliminaries 52.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 0/1 Integer Linear Programming of the Max 1-BDS problem 53 Heuristic algorithms and an exact algorithm 73.1 Reduction rules . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Heuristic algorithms . . . . . . . . . . . . . . . . . . . . . . 123.2.1 DROP . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2.2 SELECT . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.3 IDROP . . . . . . . . . . . . . . . . . . . . . . . . . 183.2.4 ISELECT . . . . . . . . . . . . . . . . . . . . . . . . 183.3 Branch-and-reduce algorithms . . . . . . . . . . . . . . . . . 203.3.1 Discard rst . . . . . . . . . . . . . . . . . . . . . . . 213.3.2 Select rst . . . . . . . . . . . . . . . . . . . . . . . . 234 Experiment results 265 Concluding remarks 41
 [1] B. Balasundaram, Cohesive subgroup model for graph-based text mining,Proceedings of the 2008 IEEE Conference on Automation Scienceand Engineering, pp. 989{994, 2008.[2] B. Balasundaram, S. Chandramouli, and S. Trukhanov, Approximationalgorithms 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 insocial network analysis: The maximum k-plex problem, OperationsResearch 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, Onbounded-degree vertex deletion parameterized by treewidth, DiscreteApplied Mathematics, 160 (2012), pp. 53{60.[7] R. van Bevern, H. Moser, and R. Niedermeier, Approximation andtidying{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-parameteralgorithms 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: analysisof a branch-and-reduce algorithm for the maximum bounded-degree-1 set problem, in proceedings of the 29th Workshop on CombinatorialMathematics and Computation Theory, pp. 136{145, 2012.[10] M.-S. Chang and L.-J. Hung, Moderately exponential time approximationalgorithms for the maximum bounded-degree-1 set problem, inProceedints of the 30th Workshop on on Combinatorial Mathematicsand 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 ofSTOC 2002, pp. 33{42.[13] M. R. Fellows, J. Guo, H. Moser, and R. Niedermeier, A generalizationof Nemhauser and Trotter's local optimization theorem, Journal ofComputer and System Sciences, 77 (2011), pp. 1141{1158.[14] J. Guo, C. Komusiewicz, R. Niedermeier, and J. Uhlmann, A morerelaxed 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. Hu ner, H. Moser, and R. Niedermeier, Isolationconcepts for eciently enumerating dense subgraphs, Theoretical Com-puter Science, 410 (2009), pp. 3640{3654.[17] B. McClosky and I.V. Hicks, Combinatorial algorithms for the maximumk-plex problem, Journal of Combinatorial Optimization, 23(2012) pp. 29{49.[18] H. Moser, R. Niedermeier, and M. Sorge, Exact combinatorial algorithmsand experiments for nding maximum k-plexes, Journal ofCombinatorial Optimization, 24 (2012), pp. 347{373.[19] N. Nishmura, P. Ragde, and D. M. Thilikos, Fast xed-parametertractable 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 ofthe clique concept, The Journal of Mathematical Sociology 6 (1978),pp. 139{154.[21] S. Trukhannov, Novel approaches for solving large-scale optimizationproblems on graphs, PhD Thesis, A&M University, Texas, 2008.[22] B.Wu and X. Pei, A parallel algorithm for enumerating all the maximalk-plexes, Proceedings of PAKDD 2007, LNAI 4819 (2007), pp. 476{483.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 最密k 集合問題在最大分支度三之圖上的正確解演算法 2 分支化約演算法的複雜度分析：使用衡量與征服技巧

 無相關期刊

 1 最大有限分支度d集合問題之啟發式演算法設計與分析 2 藉由改變最少正負號和刪點以平衡完全圖 3 最小三命中集合問題之新啟發式演算法設計與分析 4 虧損公司董監自肥與盈餘管理 5 對社會網路的抽樣方法 6 高階經理人之薪酬與績效在不同景氣循環下之研究-以國內銀行業為例 7 公司重整與銀行債權確保—實務案例的觀察 8 高階經理人更換前後影響策略聯盟因素之比較－以台日企業合作為例 9 藉由實驗的方式研究圖論上邊修改問題 10 叢集圖編修問題的固定參數演算法 11 交叉立方體條件式容錯漢米爾頓迴路 12 模擬社會網路生成的改進模型 13 垃圾郵件收集方式有效性評估與樣本減量 14 針對電子商務應用的一些認證之研究 15 多媒體教學應用於國中補校學生英語學習之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室