Testing Connectivity of Graphs
Date Issued
2006
Date
2006
Author(s)
Hsuan-Chang Chen
DOI
en-US
Abstract
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.
Subjects
連通圖
近似
測試
圖形演算法
Property Testing
Graph algorithm
Connected graph
Approximation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93922117-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):e572715866441de11c989781b34751a8