An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

DOI10.1007/BF02935789zbMath1082.05089MaRDI QIDQ2574326

Anita Saha, Madhumangal Pal, Tapan Kumar Pal

Publication date: 21 November 2005

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

zbMATH Keywords

Parallel algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ \(L(0,1)\)-labelling of permutation graphs ⋮ Genetic algorithmic approach to find the maximum weight independent set of a graph ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a maximum independent set in a permutation graph
• A unified approach to parallel depth-first traversals of general trees
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• The weighted maximum independent set problem in permutation graphs
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Faster optimal parallel prefix sums and list ranking
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Parallel Prefix Computation
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs
• Maximum weightk-independent set problem on permutation graphs
• An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

This page was built for publication: An efficient PRAM algorithm for maximum-weight independent set on permutation graphs