Efficient computation of sparse structures |
| |
| Authors: | David G. Harris Ehab Morsy Gopal Pandurangan Peter Robinson Aravind Srinivasan |
| |
| Affiliation: | 1. Department of Computer Science, University of Maryland;2. Division of Mathematical Sciences, Nanyang Technological University, Singapore;3. Department of Mathematics, Suez Canal University, Ismailia, Egypt;4. Department of Computer Science, Brown University, Providence, Rhode Island;5. Department of Computer Science, Royal Holloway, University of London, United Kingdom;6. Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland |
| |
| Abstract: | Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault‐tolerance or load‐balance properties. We propose and study “low‐average degree” or “sparse” versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 322–344, 2016 |
| |
| Keywords: | graph algorithms distributed algorithms randomization approximation algorithms maximal independent set lower bounds |
|
|
