A new backtracking algorithm for generating the family of maximal independent sets of a graph

DOI10.1016/0898-1221(83)90115-3zbMath0528.05058OpenAlexW2052864165MaRDI QIDQ786833

Emmanuel Loukakis

Publication date: 1983

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(83)90115-3

zbMATH Keywords

branch-and-search algorithmfamily of maximal independent sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items

Solving the maximum clique problem using a tabu search approach, STABULUS: A technique for finding stable sets in large graphs with tabu search, Maximal independent sets in caterpillar graphs, Finding maximum cliques in arbitrary and in special graphs, The maximum clique problem

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique detection for nondirected graphs: Two new algorithms
• A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
• A note on the complexity of the chromatic number problem
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• An Algorithm for the Chromatic Number of a Graph
• An Analysis of Some Graph Theoretical Cluster Techniques
• An algorithm for the chromatic number of a graph
• The Enumeration of Maximal Cliques of Large Graphs
• Clique Detection Algorithms Based on Line Addition and Line Removal
• Corrections to Bierstone's Algorithm for Generating Cliques
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs