請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9992
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂 | |
dc.contributor.author | Sheng-Yao Tseng | en |
dc.contributor.author | 曾聖耀 | zh_TW |
dc.date.accessioned | 2021-05-20T20:54:22Z | - |
dc.date.available | 2011-08-11 | |
dc.date.available | 2021-05-20T20:54:22Z | - |
dc.date.copyright | 2011-08-11 | |
dc.date.issued | 2011 | |
dc.date.submitted | 2011-08-01 | |
dc.identifier.citation | [1] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast
estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. [2] Richard D. Alba. A graph-theoretic de nition of a sociometric clique. Journal of Mathematical Sociology, 3:3-113, 1973. [3] Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. J. Comput. Syst. Sci., 54(2):255-262, 1997. [4] Timothy Chan. All-pairs shortest paths with real weights in O(n3/log n) time. Algorithmica, 50:236-243, 2008. [5] Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39(5):2075-2089, 2010. [6] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. [7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 2nd edition. MIT Press, Cambridge, MA, 2 edition, 2001. [8] Pierluigi Crescenzi, Roberto Grossi, Claudio Imbrenda, Leonardo Lanzi, and Andrea Marino. Finding the diameter in real-world graphs - experimentally turning a lower bound into an upper bound. In Mark de Berg and Ulrich Meyer, editors, ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 302-313. Springer, 2010. [9] Edsger W. Dijkstra. A note on two problems in connexion with graphs. Nu- merische Mathematik, 1:269-271, 1959. [10] Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM J. Comput., 29(5):1740-1759, 2000. [11] P. Erd}os and A. R enyi. On random graphs. I. Publ. Math. Debrecen, 6:290-297, 1959. [12] Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75 - 174, 2010. [13] Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):83-89, 1976. [14] Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Inf. Comput., 134(2):103-139, 1997. [15] Zvi Galil and Oded Margalit. All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci., 54(2):243-254, 1997. [16] Yijie Han. Improved algorithm for all pairs shortest paths. Inf. Process. Lett., 91(5):245-250, 2004. [17] Yijie Han. An O(n3(log log n/log n)5/4) time algorithm for all pairs shortest path. Algorithmica, 51(4):428-434, 2008. [18] Donald B. Johnson. E cient algorithms for shortest paths in sparse networks. J. ACM, 24:1-13, January 1977. [19] D.R. Karger, D. Koller, and S.J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. Foundations of Computer Science, Annual IEEE Symposium on, 0:560-568, 1991. [20] L.R. Kerr. The e ect of algebraic structure on the computational complexity. PhD thesis, Cornell University, Ithaca, N.Y., 1970. [21] R. Luce. Connectivity and generalized cliques in sociometric group structure. Psychometrika, 15:169-190, 1950. [22] Cl emence Magnien, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. ACM Journal of Experimental Algorithmics, 13, 2008. [23] Catherine C. McGeoch. All-pairs shortest paths and the essential subgraph. Algorithmica, 13(5):426-441, 1995. [24] Kurt Mehlhorn and Ulrich Meyer. External-memory breadth- rst search with sublinear i/o. In Rolf H. Möhring and Rajeev Raman, editors, ESA, volume 2461 of Lecture Notes in Computer Science, pages 723-735. Springer, 2002. [25] Robert J. Mokken. Cliques, clubs and clans. Quality & Quantity, 13(2):161-173, April 1979. [26] M. E. J. Newman. The structure of scienti c collaboration networks. Pro- ceedings of the National Academy of Sciences of the United States of America, 98(2):404-409, January 2001. [27] Raimund Seidel. On the all-pairs-shortest-path problem. In STOC, pages 745- 749. ACM, 1992. [28] Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In FOCS, pages 605-615, 1999. [29] Philip M. Spira. A new algorithm for nding all shortest paths in a graph of positive arcs in average time O(n2 log2n). SIAM J. Comput., 2(1):28-32, 1973. [30] Tadao Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters, 43(4):195 - 199, 1992. [31] Tadao Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Kyung-Yong Chwa and J. Ian Munro, editors, COCOON, volume 3106 of Lecture Notes in Computer Science, pages 278-289. Springer, 2004. [32] Tadao Takaoka. An O(n3 log log n/log n) time algorithm for the all-pairs shortest path problem. Information Processing Letters, 96(5):155 - 161, 2005. [33] Gideon Yuval. An algorithm for nding all shortest paths using n2:81 in niteprecision multiplications. Inf. Process. Lett., 4(6):155-156, 1976. [34] Uri Zwick. Exact and approximate distances in graphs - a survey. In Friedhelm Meyer auf der Heide, editor, ESA, volume 2161 of Lecture Notes in Com- puter Science, pages 33-48. Springer, 2001. [35] Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. [36] Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In Rudolf Fleischer and Gerhard Trippen, editors, Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 841-843. Springer Berlin / Heidelberg, 2005. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9992 | - |
dc.description.abstract | 我們研究完全子圖之最遠距離(clique diameter)問題。給定一個無向、無權重圖,並同時給定一個集合,集合包含圖上所有給定的完全子圖,該問題問其中任兩組完全子圖間之最遠距離為何?由於完全子圖可以代表一個理想的社群,其中每一成員均關聯於其它成員,本問題即是詢問圖上各社群之距離,以及距離最遠的一組社群。假設圖上有n個點與m個邊,同時給定r個完全子圖,我們設計一個O(r(n+m))時間且最多誤差為1的近似演算法,並提供一個轉換方式,讓我們得以運用全點最短路徑演算法來解決我們的研究問題。 | zh_TW |
dc.description.abstract | We study the clique diameter problem. Given an undirected, unweighted graph containing a set of cliques, we are interested in finding the maximum distance among all pairs of cliques. In the context of social network analysis, a clique represents an ideal community, a clique distance represents the sparsity between the two communities, and a clique diameter indicates the farthest distance among the social network. Let n denote the number of nodes, m denote the number of edges and r denote the number of given cliques. We provide an O(r(n + m)) time algorithm to compute approximate clique distances with additive error of one. Another contribution is a reduction which transforms any instance of the clique distance problem into an instance of the all-pairs shortest paths problem. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T20:54:22Z (GMT). No. of bitstreams: 1 ntu-100-R98922095-1.pdf: 2140552 bytes, checksum: bbdc4aa9ffd08c2ab3dcd62a335194b5 (MD5) Previous issue date: 2011 | en |
dc.description.tableofcontents | 1 Introduction 1
2 Preliminaries 4 2.1 Basic Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 All-Pairs Shortest Paths Problem . . . . . . . . . . . . . . . . 6 2.2.2 Distance Matrix Multiplication . . . . . . . . . . . . . . . . . 7 2.2.3 Approximate Results . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.4 Diameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Clique Distance and a Straightforward Algorithm 13 3.1 Problem Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 A Straightforward Algorithm . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Some Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 On Transformation to All-Pairs Shortest Paths Problem 21 4.1 A Failed Attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Concluding Remarks 25 | |
dc.language.iso | en | |
dc.title | 在大型網路圖上計算完全子圖之最遠距離 | zh_TW |
dc.title | Computing the Maximum Clique Distance on a Large-Scale Network | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 張雅惠,王弘倫 | |
dc.subject.keyword | 圖形演算法,完全子圖,全點最短路徑,矩陣相乘,廣度優先搜尋, | zh_TW |
dc.subject.keyword | graph algorithm,clique,all-pairs shortest paths,matrix multiplication,breadth-first search, | en |
dc.relation.page | 30 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2011-08-02 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf | 2.09 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。