跳到主要內容

臺灣博碩士論文加值系統

(3.236.110.106) 您好!臺灣時間:2021/07/25 08:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:巫冠翰
研究生(外文):Guan-Han Wu
論文名稱:最密k 集合問題在最大分支度三之圖上的正確解演算法
論文名稱(外文):An Exact Algorithm for the Densest k-set Problem on Maximum Degree Three Graphs
指導教授:張貿翔張貿翔引用關係吳邦一
指導教授(外文):Maw-Shang ChangBang Ye Wu
口試委員:張貿翔吳邦一黃耀廷賴泳伶
口試委員(外文):Maw-Shang ChangBang Ye WuYao-Ting HuangYung-Ling Lai
口試日期:2012-07-20
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:37
中文關鍵詞:正確解演算法最密k集合問題最密k子圖問題分支化約演算法最大分支度3圖
外文關鍵詞:Exact AlgorithmDensest k-setDensest k-subgraphBranch-and-Reduce AlgorithmMaximum Degree 3 Graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:221
  • 評分評分:
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:0
在一個無向圖 G=(V,E)之中,最密k集合為一個V的子集S,其點數為k,並且S所導出(induce)之子圖邊數為所有k集合中最多的,在社群網路中,最密k集合通常被認定為在此網路中關係密切的一群,最密k集合問題即使在最大分支度3的圖上,仍然為一個NP-Hard問題,在這篇論文中,我們定義了一個最密k集合問題的變化問題,並稱之為最密受限制k集合問題,當一個k集合導出的子圖之最小分支度為2時,我們稱之為受限制k集合,而最密受限制k集合導出之子圖邊數為所有受限制k集合中邊數最多的,我們在文中將證明如果我們有一個演算法可以在 O(f(n)) 時間複雜度之內解決最密受限制k集合問題,那我們將有一個複雜度為 O(poly(n)*f(n))的演算法解決最密k集合問題,我們也提出當我們的圖最大分支度為3,我們有一個時間複雜度為 O*(1.7485^n) 的演算法來解決最密受限制k集合問題。
A densest k-set S in an undirected graph G=(V, E) is a vertex set of size k such that the number of edges in the subgraph induced by S is maximum among all subgraphs induced by k vertices. The concept of densest k-set is often used to define cohesive subgroups in a social network. The Densest k-Set problem is NP-hard even for graphs of maximum degree three. In this thesis, we define a variant problem of the Densest k-Set problem called the Densest Restricted k-Set problem. A vertex set S is said restricted if the graph induced by S has minimum degree at least two. The Densest Restricted k-Set problem is to find a densest k-set among all restricted vertex sets of size k. We show that if there is an algorithm that solves the Densest Restricted k-Set problem in O(f(n)) time, by taking the algorithm as a subroutine the Densest k-Set problem can be solved in time O(poly(n)*f(n)). Moreover, we give a polynomial-space algorithm running in time O*(1.7485^n) for the Densest Restricted k-Set problem on graphs of maximum degree~three.
English Abstract
Content ....................................1
List of Tables .............................2
List of Figures ............................3
Introduction ...............................4
Preliminaries ..............................10
An O*(1.7485n)-time algorithm ..............14
The Densest Restricted k-set problem ....14
An O*(1.7485n)-time algorithm ....16
Conclusion remarks .........................29
Bibliography ...............................31
[1] S. Arora, D. Karger, and M. Karpinski, Polynimial time approximation schemes for dense instances of NP-hard problems, In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 284–293,1995.

[2] R. Andersen and K. Chellapilla, Finding dense subgraphs with size bounds, In Proceedings of WAW'09, pp. 25–36, 2009.

[3] Y. Asahiro, K. Iwama, H. Tamaki and T. Tokuyama, Greedily finding a dense subgraph, Journal of Algorithms, 34 (2000), pp. 203–221.

[4] R.E. Bellman, Dynamic Programming, Princeton University Press, Princton, NJ, 1957.

[5] J. Backer and J. M. Keil, Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs, Information Processing Letters 110 (2010), pp. 635–638.

[6] A. Bhaskara, M. Charika, E. Chlamtac, U. Feige, and A. Vijayaraghavan, Detecting high log-densities: an O(n^(1/4))-approximation algorithms for the densest k-subgraph, In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'10), pp. 201–210, 2010.

[7] A. Billonnet and F. Roupin, A deterministic approximation algorithm for the densest k-subgraph problem, Journal of Operational Research 3 (2008), pp. 301–314.

[8] N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th. Paschos, Exact and approximation algorithms for densest k-subgraph, Technique report

[9] L. Cai. Parameterized complexity of cardinality constrained optimization problems. Comput. J., 51 (2008) 102–121.

[10] L. Cai, S. M. Chan, and S. O. Chan, Random separation: a new method for solving fixed-cardinality optimization problems, Proceedings of IWPEC 2006 LNCS 4169 (2006), pp. 239–250.

[11] M.-S. Chang, L.-H. Chen, L.-J. Hung, P. Rossmanith, and G.-H. Wu, Exact algorithms for problems related to the densest k-set problem, Proceedings of NCS 2011: Algorithms and Bioinformatics Workshop, pp. 1–9, 2011.

[12] D. Z. Chen, R. Fleischer, and Jian Li, Densest k-subgraph approximation on intersection graphs, In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA'10), pp. 83–93, 2010.

[13] D. Corneil, Y. Perl, Clustering and domination in perfect graphs, Discrete Appl. Math. 9 (1984) 27–40.

[14] R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theor. Comput. Sci. 141 (1995) 109–131

[15] K. Dudzinski, S. Walukiewicz, Exact methods for the knapsack problem and its generalizations, Eur. J. Oper. Res., 28 (1987), pp. 3–21.

[16] U. Feige and M. Seltser, On the dense k-subgraph problem, Technical Report, The Weizmann Institute, 1997.

[17] U. Feige, G. Kortsarz, and D. Peleg, The dense k-subgraph problem, Algorithmica 29 (2001), pp. 410–421.

[18] F. V. Fomin and D. Kratsch, Exact Exponential Algorithms, Springer, 2010.

[19] A. Goldberg, Finding a maximum density subgraph, Technical Report UCB/CSB 84/171, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1984.

[20] J. Guo, R. Niedermeier, and S. Wernicke, Parameterized complexity of vertex cover variants, Theor. Comput. Syst. 41 (2007) 501–520.

[21] Q. Han, Y. Ye, and J. Zhang, An improved rounding method and semidefinite programming relaxation for graph partition, Mathematical Programming 92 (2002), pp. 509–535.

[22] R. Hassin, S. Rubinstein, and A. Tamir, Approximation algorithms for maximum dispersion, Operations Research Letters 21 (1997), pp. 133–137.

[23] J. M. Keil, and T. Brecht, The complexity of clustering in planar graphs, J. Combin. Math. Combin. Comput. 9 (1991) 155–159.

[24] S. Khot, Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique, SIAM Journal on Computing 36 (2006), pp. 1025–1071.

[25] M. Liazi, I. Milis, and V. Zissimopoulos, The densest k-subgraph problem on clique graphs, J. Comb. Optim. 14 (2007) 465–474.

[26] M. Liazi, I. Milis, and V. Zissimopoulos, A constant approximation algorithm for the denest k-subgraph problem on chordal graphs, Information Processing Letters 108 (2008), pp. 29–32.

[27] T. Nonner, PTAS for densest k-subgraph in interval graphs, Manuscript, 2011.

[28] S. S. Ravi, D. J. Rosenkrantz, G. K. Tayi, Heuristic and special case algorithms for dispersion problems, Operations Research 42 (1994), pp. 299–310.

[29] A. Srivastav and K. Wolf, Finding dense subgraphs with semidefinite programming, In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 181–191, 1998.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top