Apply Probability and Graph Theory to Develop Algorithms Regarding Testing L(M,N)-Labeling

Property testing is an important and active topic in algorithm research. Many recent research results concern the testing of graph properties. For a fixed property P and any graph G, we want to determine whether G has property P. For example, the object can be a graph and the property can be connectedness. Michael A. Bender and Dana Ron construct a restricted tester on the strong connectivity of directed graphs. Although this method has restrictions, the task can be performed by querying the input directed graph in very few places. For a fixed digraph H with at least one edge, let H P denote the property of the input digraph being H-free. In other words, the digraph G has H P if and only if it contains no subgraphs isomorphic to H. Noga Alon and Asaf Shapira proved that H P is testable. Noga Alon, Eldar Fischer, Ilan Newman and Asaf Shapira proved a very general result for undirected graphs, which says that the property defined by having any given Szemeredi-partition is testable with a constant number of queries. These researchers use many powerful mathematical tools and develop many new proof techniques. Based on these results, we construct a randomized algorithm for testing directed graphs with an H-free k-induced subgraph. In order to further develop these ideas, this project plan to design some randomized algorithm to a friendly test some important graphic properties. For example, we expect to test whether a graph is L(2,1)-labeling and extend the result to L(k,1)-labeling L(m,n)-labeling or even L(m,n)-labeling.[[abstract]]對於圖(graph)的性質測定(property testing)問題，是近年來在演算法領域非常重要而且 活躍的研究題目。在僅能知道一個圖的有限細節之前提下，許多學者希望能夠測定任何 一個圖是否具有某個事先指定的性質，例如任一個圖是否具有連通性(connectedness of graphs)。而Michael A. Bender 與Dana Ron 便發展了一個測試bounded degree 有向圖 (directed graph)是否連通的方法，雖然這個方法在使用上有些許限制，但是僅需要知道 輸入圖之極小部分的細節便可以進行性質測定。除了上述的題目外，Noga Alon 與Asaf Shapira 則發展了一個性質測定演算法，去測定任一個有向圖是否存在一個特定的子圖 (subgraph)。Noga Alon, Eldar Fischer, Ilan Newman 與Asaf Shapira 等人證明了任何一個 無向圖(undirected graph)的性質，如果可以對應在一個Szemerkedi 分割上，那麼這個性 質就存在一個隨機演算法可以作性質測定。前述的這些研究成果利用了許多強有力的數 學工具，並發展了許多新穎的證明技巧。在這些研究的基礎上，筆者發展了一個有效率 的隨機演算法，對於滿足某些條件的有向圖H，可以測定任一個有向圖是否包含一個子 圖是滿足H-free 的性質，也就是說在這個子圖中沒有任何一個子圖(也就是子圖的子圖) 與H 為圖同構(isomorphism)。本計畫是基於之前的研究成果，做更進一步的發展，並 預期能夠解決一些重要的圖論性質之測定的問題，例如L(2,1)編碼(L(2,1)-labeling) 並將這些結果推廣到更一般性的L(k,1)編碼、L(m,n)編碼甚至( , ,..., ) 1 2 k L m m m 上