An efficient PRAM algorithm for maximum-weight independent set on permutation graphs (Q2574326): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A unified approach to parallel depth-first traversals of general trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Faster optimal parallel prefix sums and list ranking / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel Prefix Computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3328583 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient algorithm to generate all maximal independent sets on trapezoid graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding a maximum independent set in a permutation graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4718828 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A sequential algorithm for finding a maximum weight<i>K</i>-independent set on interval graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A parallel algorithm to generate all maximal independent sets on permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4222504 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum weight<i>k</i>-independent set problem on permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The weighted maximum independent set problem in permutation graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs / rank
 
Normal rank

Latest revision as of 12:07, 11 June 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
    0 references
    0 references
    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
    0 references
    Parallel algorithms
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references