Property Testing on Directed Graphs and Abelian Groups
Date Issued
2009
Date
2009
Author(s)
Ti, Yen-Wu
Abstract
Bender and Ron construct a restricted tester on the strong connectivity of digraphs (we call it the BR tester). We generalize the BR tester to test the strong connectivity of digraphs.or any digraph H and a digraph G being far from any H-free digraph, Alon and Shapira prove a lower bound of the number of H in G. After solving the problem of testing the strong connectivity of digraphs, we use Alon and Shapira''s result to construct a randomized algorithm for testing digraphs with an H-free k-induced subgraph.ur strong connectivity tester has no restriction but must query about the input more times than the restricted BR tester. Suppose an input digraph satisfies the restrictions of the BR tester, using the BR tester to test the strong connectivity of this input digraph is more e±cient than using our strong connectivity tester. If we want to test the strong connectivity of a digraph, our randomized algorithm for testing digraphs with an H-free k-induced subgraph can help us determine which tester should be used to test the strong connectivity of the digraph: the BR tester or our strong connectivity tester. generator set for a finite group is a subset of the group elements such that repeated multiplications of the generators alone can produce all the group elements.he number of generators of an abelian group is an important issue in many studies. In most cases, it is not easy to identify whether a group-like structure is an abelian group with k generators for a constant k. We construct an efficient randomized algorithm that, given a finite set with a binary operation, tests if it is an abelian group with a k-generator set. If k is not too large, the query complexity of our algorithm is polylogarithmic in the size of the groundset. Otherwise the query complexity is at most the square root of the size of the groundset.
Subjects
Property testing
Strong connectivity
H-free subgraph
Abelian
Generator
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D91922010-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):8f3c3fbee9b2947dfa700d4b1a0705ca