Constructing a Maximal Independent Set in Parallel
Copyright policy )Constructing a Maximal Independent Set in Parallel
Summary: The problem of constructing in parallel a maximal independent set of a given graph is considered. A new deterministic NC-algorithm implemented in the EREW PRAM model is presented. On graphs with n vertices and m edges, it uses \(0((n+m)/\log n)\) processors and runs in \(0(\log^ 3\) n) time. This reduces by a factor of log n both the running time and the processor count of the previously fastest deterministic algorithm that solves the problem using a linear number of processors.
EREW PRAM model, Graph theory (including graph drawing) in computer science, deterministic NC-algorithm, Models of computation (Turing machines, etc.), maximal independent set
EREW PRAM model, Graph theory (including graph drawing) in computer science, deterministic NC-algorithm, Models of computation (Turing machines, etc.), maximal independent set
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).61 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!