An efficient algorithm to generate all maximal independent sets on trapezoid graphs

DOI10.1080/00207169908804777MaRDI QIDQ4240618zbMATH OpenOpenAlexFDO

Authors Mrinmoy Hota, Madhumangal Pal, Tapan K. 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

zbMATH Keywords

maximal independent sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• On generating all maximal independent sets
• Generate all maximal independent sets in permutation graphs
• Efficient maximum matching algorithms for trapezoid graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Dominations in trapezoid graphs
• 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 Parallel Algorithms for Chordal Graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Finding maximum cliques in circle graphs
• Generate all maximal independent sets in permutation graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the structure of trapezoid graphs
• Recognizing circle graphs in polynomial time
• Trapezoid graphs and their coloring

Cited in

(8)

• An optimal PRAM algorithm for a spanning tree on trapezoid graphs.
• A general method for generating all maximal independent sets of a graph
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Maximal independent sets in caterpillar graphs
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• Maximal independent sets in grid graphs

This page was built for publication: An efficient algorithm to generate all maximal independent sets on trapezoid graphs

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