Premium
Efficient computation of sparse structures
Author(s) -
Harris David G.,
Morsy Ehab,
Pandurangan Gopal,
Robinson Peter,
Srinivasan Aravind
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20653
Subject(s) - computer science , complement (music) , extant taxon , computation , distributed algorithm , key (lock) , fault tolerance , upper and lower bounds , graph , theoretical computer science , randomized algorithm , algorithm , contrast (vision) , expander graph , mathematics , distributed computing , artificial intelligence , mathematical analysis , biochemistry , chemistry , computer security , evolutionary biology , complementation , biology , gene , phenotype
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