A parallel algorithm to generate all maximal independent sets on permutation graphs

DOI10.1080/00207169808804664MaRDI QIDQ4392327zbMATH OpenOpenAlexFDO

Authors Madhumangal Pal

Publication date 8 June 1998

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207169808804664

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Generate all maximal independent sets in permutation graphs
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• The weighted maximum independent set problem in permutation graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A unified approach to parallel depth-first traversals of general trees
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Fast Parallel Algorithms for Chordal Graphs
• Finding maximum cliques in circle graphs
• Generate all maximal independent sets in permutation graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Optimal parallel time bounds for the maximum clique problem on intervals
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• Some parallel algorithms on interval graphs
• The weighted maximum independent set problem in permutation graphs

Cited in

(7)

• Generating all maximal independent sets on trees in lexicographic order
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Generate all maximal independent sets in permutation graphs
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• L(0,1)-labelling of permutation graphs

This page was built for publication: A parallel algorithm to generate all maximal independent sets on permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4392327)