Thumbnail
Access Restriction
Open

Author Itai, Alon
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Deterministic Algorithm ♦ Simple Randomized Parallel Algorithm ♦ Maximum Degree ♦ Deterministic Construction ♦ Fast Parallel Time ♦ Erew-pram Model ♦ Concurrent-read Concurrent-write Pram ♦ Painvise Independent Choice ♦ Expected Running Time ♦ Various Combinatorial Object ♦ Randomized Combinatorial Algorithm ♦ Probabilistic Argument ♦ Independent Random Choice ♦ Exclusive-read Exclusive-write Pram
Abstract A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with 0 ( 1 E 1 d,,) processors is O(log n), where d,, denotes the maximum degree. On an exclusive-read exclusive-write PRAM with 0 ( 1 El) processors the algorithm runs in O(log2n). Previously, an O(log4n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log2n) by M. Luby. In both cases randomized algorithms depending on painvise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 1986-01-01