A parallel algorithm to generate all maximal independent sets on permutation graphs
From MaRDI portal
Publication:4392327
DOI10.1080/00207169808804664zbMath0896.68077OpenAlexW1990418828MaRDI QIDQ4392327
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
Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Distributed algorithms (68W15)
Related Items (5)
Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ \(L(0,1)\)-labelling of permutation graphs ⋮ 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
Cites Work
- Unnamed Item
- Some parallel algorithms on interval graphs
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- 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
- 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
- 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
- A New Algorithm for Generating All the Maximal Independent Sets
- Generate all maximal independent sets in permutation graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
This page was built for publication: A parallel algorithm to generate all maximal independent sets on permutation graphs
