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

DOI10.1016/0898-1221(83)90115-3MaRDI QIDQ786833zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3504320 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• 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
• Algorithm 457: finding all cliques of an undirected graph
• 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
• Clique Detection Algorithms Based on Line Addition and Line Removal
• Clique detection for nondirected graphs: Two new algorithms
• Corrections to Bierstone's Algorithm for Generating Cliques
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• On cliques in graphs
• The Enumeration of Maximal Cliques of Large Graphs

Cited in

(5)

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

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: A new backtracking algorithm for generating the family of maximal independent sets of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786833)