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

DOI10.1016/0898-1221(83)90115-3zbMath0528.05058MaRDI 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 algorithm; family of maximal independent sets

Mathematics Subject Classification ID

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

05C99: Graph theory

68W99: Algorithms in computer science

Related Items

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

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