An efficient PRAM algorithm for maximum-weight independent set on permutation graphs (Q2574326): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 07:37, 5 March 2024
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
