劉邦鋒Liu, Pangfeng臺灣大學:資訊工程學研究所蔡孟宗Tsai, Meng-TsungMeng-TsungTsai2010-05-182018-07-052010-05-182018-07-052008U0001-2207200822155700http://ntur.lib.ntu.edu.tw//handle/246246/183614在論文中，們發展了新的演算法來計算給定圖的三角子圖數。前已知最有效率的撥結點演算法需要$O(m^{3/2})$本指令的計算時間及$Theta(m)$記憶體空間。合廣為人知的四蘇聯人演算法，以得到稍微進一步的演算法需要$O(m^{3/2}/log^{1/2}m)$聚指令的計算時間及$Theta(m)$記憶體空間。而僅有部份的中央處理器支援群聚指令，有支援的情況下，聚指令被視為基本指令，不支援的情況下，聚指令可以用$O(log^{(2)}g)$個基本指令完成。這論文提到的計算三角子圖中，不需要知道每個群聚指令的執行結果。用這個特性，們發展了攤還式演算法，能進一步改善了在不支援的情況下，聚指令所需的基本指令僅須$o(log^{(3)}g)$個指令完成。管在理論分析或是實驗數據上，們的攤還式演算法均勝出，的幅度是$omega(log^{1/2}m/log^{(4)}m)$。In this paper, we develop a new algorithm to count the number of triangles in a graph $G(n, m)$.he latest efficient algorithm, Forward Algorithm, needs $O(m^{3/2})$ basic instructions'' execution timend $Theta(m)$ memory space.ith the combination of the well-known Four-Russians'' Algorithm, we obtain an algorithm that requiresO(m^{3/2}/log^{1/2} m)$ execution of the population count procedure using $Theta(m)$ memory space.ome CPUs support population count directly.n such cases, the population count can be executed with one instruction;therwise, an alternative method should be employed.he known best one is named as extit{bitwise twiddling} method,hich can be executed with $Theta(log^{(2)}g)$ basic instructions.wing to it is not necessary to exactly know the result of each population count, we can replaceach population count with an amortized population count.herefore, we also develop an efficient algorithm to fast execute the amortized population count.ased on the theoretic analysis, we conclude that the amortized population count can be executed witho(log^{(3)}g)$ basic instructions.esides, the experiment result also shows the performance of our amortized population count is betterhan others.s a result, our triangle counting algorithm is faster than the previous known best one by factor $omega(g^{1/2} / log^{(3)} g)$ where $g = Omega(log m)$.Approval Page ibstract iihinese Abstract iinglish Abstract iiiable of Contents ivontents ivist of Figures viist of Tables vii Introduction 1.1 Framework 1.2 Structure of this Thesis 3 Preliminaries 5.1 Triangle Counting 6.1.1 Strassen-like Algorithm 6.1.2 Four-Russians''-like Algorithm 7.1.3 Forward Algorithm 8.2 Population Counting 9.2.1 Bitwise Twiddling Algorithm 10.2.2 Frequency Division Algorithm 11 Proposed Algorithms 14.1 Other Viewpoints 14.2 Modi ed Forward Algorithm 16.3 Fast Amortized Population Counting 17 Experiment Results 20.1 Population Counting Algorithms 20.2 Amortized Population Counting Algorithms 23.3 Triangle Counting Algorithms 24.3.1 Man-Made Graphs 25.3.2 Real World Graphs 27 Concluding Remarks 28.1 Possible Future Work 28ibliography 29application/pdf760226 bytesapplication/pdfen-US三角子圖計算稀疏圖高效演算法群聚指令除頻原則triangle countingsparse graphefficient algorithmpopulation countingfrequency division principlethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183614/1/ntu-97-R95922065-1.pdf