分散式圖形同構演算法之設計與實驗分析

A Distributed Graph Isomorphism Algorithm - Design and Experiment

蔡翔宇(Shiang-Yu Tsai)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.02270

摘要

科技的日新月異，不只為人類社會帶來變遷，連帶的在計算機科學中，也產生了了許多新的研究領域與問題。然而，許多新的研究問題看似與傳統無關，但其實是可以轉換為計算機領域中，研究已久的理論問題。
在計算機領域中，圖論（graph theory）是門重要的學問。幾乎各個計算機領域的主要問題，都可模塑到圖形的問題上，進而研究該問題的複雜度以及演算法。對於圖形（graph）的研究，已經有數百年的歷史；而近代的數學家及計算機科學家，則致力於探討圖形問題之複雜度，以及多項式時間演算法。
圖形理論中一個重要的問題，便是「圖形同構」（graph isomorphism）。本問題尚未找出多項式時間的演算法，也尚未被證明是否為NP-Complete之問題。然而，在工程應用上，許多重要的問題，可以簡化為圖形同構問題，也因此，許多經驗性的（heuristic）演算法被設計出來，以期在大部分普遍的情況下，能較有效率的解決圖形同構問題。
另外，隨著網路及運算的普及，分散式系統也漸漸的成為科學運算的重要途徑。藉由把一主要工作分成數個次要工作，交給每個運算節點（node），希望可以達到節省運算時間的目的。相關的論述及研究已有許多成果。
本文主要探討：在Brendan McKay提出的nauty演算法架構下，如何以分散式運算技術，改善其執行效率，並針對實驗結果，討論該演算法在分散式環境中之有利之處。

關鍵字

分散式 ； 圖形同構 ； 演算法

並列摘要

無資料

並列關鍵字

distributed algorithm ； isomorphism

參考文獻

[1] J. R. Ullmann, “An algorithm for subgraph isomorphism”, Journal of the ACM, Volume 23, Issue 1, pp. 31-42, January 1976.

[2] D. C. Schmidt, L. E. Druffel, “A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices”, Journal of the ACM, Volume 23, Issue 3, pp. 433-445, July 1976.

[4] B. McKay, “Practical graph isomorphism”, Congr. Numer. 30, pp. 45-87, 1981.

[5] T. Miyazaki, “The complexity of Mckay's canonical labeling algorithm”, In Groups and Computation II, pp. 239-256, 1995.

[8] N. Giansiracusa, “Determining graph isomorphism via canonical labeling”