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

Abstract

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