Saturday, October 02, 2010

Testing cycle-freeness in bounded-degree graphs and my feelings of randomized algorithms

在圖形性質的 property testing 裡,一般不是使用 adjacency matrix,就是使用 adjacency list 來儲存一個 graph。通常 property testing 這個領域的 papers 裡,使用 adjacency list 來儲存一個 graph 的時候,會再假設 graph 的 maximum degree 至多為 d,也就是說,這樣的 model 是用來處理 bounded-degree graphs。我們可以把儲存一個 graph 的 adjacency list 當成一個 oracle,任何演算法在每個單位時間內只能得知某一個點的第幾個鄰居為哪一個點。