A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically

DOI10.1007/BF02277184zbMath0472.68029OpenAlexW177258377MaRDI QIDQ1157909

Constantine Tsouros, Emmanuel Loukakis

Publication date: 1981

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02277184

zbMATH Keywords

maximal clique

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

An algorithm for the maximum internally stable set in a weighted graph ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ Theoretical underpinnings for maximal clique enumeration on perturbed graphs ⋮ Maximal independent sets in caterpillar graphs ⋮ A new backtracking algorithm for generating the family of maximal independent sets of a graph ⋮ The maximum clique problem

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Clique detection for nondirected graphs: Two new algorithms
• Maximum internally stable sets of a graph
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• An Analysis of Some Graph Theoretical Cluster Techniques
• Corrections to Bierstone's Algorithm for Generating Cliques
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs