Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs

DOI10.1016/0196-6774(84)90037-3zbMath0544.05036OpenAlexW2077583413WikidataQ59409901 ScholiaQ59409901MaRDI QIDQ3333069

Joseph Y.-T. Leung

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90037-3

zbMATH Keywords

independent setchordal graphinterval graphcircular-arc graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Algorithms in computer science (68W99)

Related Items (19)

Coloring permutation graphs in parallel ⋮ Generating all maximal independent sets on trees in lexicographic order ⋮ Optimal separable partitioning in the plane ⋮ Path Problems in Complex Networks ⋮ Maximum weight independent set of circular-arc graph and its application ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ The complexity of colouring circle graphs ⋮ Generate all maximal independent sets in permutation graphs ⋮ Maximal independent sets in grid graphs ⋮ Counting the number of independent sets in chordal graphs ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ Maximal independent sets in caterpillar graphs ⋮ Unnamed Item ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems ⋮ Interval graphs and related topics ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs

This page was built for publication: Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs