A New Algorithm for Generating All the Maximal Independent Sets

1977/09/01 by Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi +1 · 16 citations
Computer Science · Mathematics · #Graph Theory and Algorithms #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics #Mathematics #Discrete mathematics #Graph #Bounded function #Null graph #Independent set #Graph theory #Graph power #Strength of a graph #Butterfly graph #Voltage graph #Algorithm #Line graph

paper · doi:10.1137/0206036

openalex publication_date 1977/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The problem of generating all the maximal independent sets (or maximal cliques) of a given graph is fundamental in graph theory and is also one of the most important in terms of the application of graph theory. In this paper, we present a new efficient algorithm for generating all the maximal independent sets, for which processing time and memory space are bounded by O(nmμ) and O(n+m), respectively, where n, m, and μ are the numbers of vertices, edges, and maximal independent sets of a graph.

Citations

• On cliques in graphs
• Algorithm 457: finding all cliques of an undirected graph

Cited by

• Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• New Algorithms for Enumerating All Maximal Cliques
• On generating all maximal independent sets
• The worst-case time complexity for generating all maximal cliques and computational experiments
• A note on the problem of reporting maximal cliques
• A note on the complexity of the chromatic number problem
• Enumerating maximal independent sets with applications to graph colouring
• All maximal independent sets and dynamic dominance for sparse graphs
• Generate all maximal independent sets in permutation graphs
• Generating all maximal independent sets of bounded-degree hypergraphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• On enumerating all minimal solutions of feedback problems
• Clique problem [wikipedia]
• Maximal independent set [wikipedia]