An efficient PRAM algorithm for maximum-weight independent set on permutation graphs (Q2574326)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An efficient PRAM algorithm for maximum-weight independent set on permutation graphs |
scientific article |
Statements
An efficient PRAM algorithm for maximum-weight independent set on permutation graphs (English)
0 references
21 November 2005
0 references
The authors present an efficient parallel algorithm to find a maximum weight independent set of a permutation graph of order \(n\), which takes \(O(\log n)\) time using \(O(n^2/\log n)\) processors on an EREW PRAM, provided the graph has at most \(O(n)\) maximal independent sets.
0 references
Parallel algorithms
0 references
0 references
0 references
0 references
0 references
0 references
0 references
