臺灣博碩士論文加值系統

有限分支度一集合問題 (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. Huner, 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.