An efficient algorithm to generate all maximal independent sets on trapezoid graphs
From MaRDI portal
Publication:4240618
DOI10.1080/00207169908804777zbMath0923.68094OpenAlexW2073015256MaRDI QIDQ4240618
Mrinmoy Hota, Madhumangal Pal, Tapan Kumar Pal
Publication date: 25 October 1999
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207169908804777
Related Items (7)
Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Maximal independent sets in grid graphs ⋮ An optimal PRAM algorithm for a spanning tree on trapezoid graphs. ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Maximal independent sets in caterpillar graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
Cites Work
- Unnamed Item
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Trapezoid graphs and their coloring
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- Dominations in trapezoid graphs
- On the structure of trapezoid graphs
- A sequential algorithm for finding a maximum weightK-independent set on interval 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
- On the 2-Chain Subgraph Cover and Related Problems
- Generate all maximal independent sets in permutation graphs
- A parallel algorithm to generate all maximal independent sets on permutation graphs
- Recognizing circle graphs in polynomial time
This page was built for publication: An efficient algorithm to generate all maximal independent sets on trapezoid graphs