臺灣博碩士論文加值系統

Graph connectivity is an important topic in network construction.For example, when we maintain a network which has existed for a longtime, we always want to know if the nodes of the network are still able to communicate with each other. However, a network can be a huge structure, and we don''t like to check the whole network to know the answer. So we use an approximation algorithm technique called ``property testing'' and only check a small set of nodes of the network to know whether the network is still good to use for communication.

The network can be represented by an adjacency matrix, and the query for the connection between two vertices is in $O(1)$ time. Our task is to determine whether a given input graph is connected or is ``relatively far'' from any graph having this property. Difference between graphs is measured by the fraction of the possible queries on the representation matrix. Our algorithm works in time polynomial in $frac{1}{epsilon log(1-epsilon)},$ always accepts the graph when it is connected, and rejects with high probability if the graph is $epsilon$-far from having the property. The query complexity is also polynomial in $frac{1}{epsilon log(1-epsilon)}$ whether the input graph is undirected or directed.

1. Introduction 2
2. Definitions and Notations 5
2.1 Some definitions in graph theory 5
2.2 Tester for graph properties 6
3. Testing Connectivity on Undirected Graphs 8
4. Testing Connectivity on Directed Graphs 12
5. Conclusions 17

[1] O. Goldreich, S. Goldwasser, and D. Ron. (1996) Property
Testing and Its Connection to Learning and Approximation. In Proceedings of the Thirty-Seventh Annual Symposium on Foundations of Computer Science, pp. 339--348
[2] Dinic, E.A., Karzanov, A.V. and Lomonosov, M.V (1976) On
the Structure of the System of Minimum Edges Cuts in a Graph. Studies in Discrete Optimization, pp. 290--306.
[3] D. Ron. (2001) Property Testing (A Tutorial). Handbook on Randomization, volume II (S. Rajasekaran, P. M. Pardalos, J. H. Reif and J. D. P. Rolimeds), Kluwer Academic Publishers
[4] O. Goldreich and D. Ron. (1997) Property Testing in Bounded Degree Graphs. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pp. 406--415.
[5] Hiro Ito, Yuichiro Itatsu, Hideyuki Uehara, Mitsuo
Yokoyama, and Motoyasu Ito. (2000) Location Problems Based
on Node-Connectivity and Edge-Connectivity between Nodes and
Node-Subsets. Lecture Notes in Computer Science, 1969, pp. 338--349.
[6] O. Goldreich. (2005) Contemplations on Testing Graph Properties.
http://www.wisdom.weizmann.ac.il/~oded/p testC.html
[7] M. Bender and D. Ron. (2000) Testing Acyclicity of Directed Graphs in Sublinear Time. In Proceedings of ICALP, pp. 809--820
[8] Y. Dinitz and J. Westbrook. (1998) Maintaining the Classes of 4-Edge-Connectivity in a Graph on Line. Algorithmica, 20(8), pp. 242--276.
[9] O. Goldreich and L. Trevisan. (2001) Three theorems regarding testing graph properties In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 460--469.