Algorithms for maximum independent sets

1986/09/01 by J. M. Robson, J.M Robson · 21 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Independent set #Mathematics #Time complexity #Upper and lower bounds #Vertex (graph theory)

paper · doi:10.1016/0196-6774(86)90032-5

crossref issued 1986/09/01 · crossref published 1986/09/01 · crossref published-print 1986/09/01 · openalex publication_date 1986/09/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/01/11 · openalex updated_date 2026/04/23

Citations

• Algorithm 457: finding all cliques of an undirected graph

Cited by

• Large Induced Subgraphs via Triangulations and CMSO
• Exact Algorithms for Treewidth and Minimum Fill-In
• Exact Algorithms for NP-Hard Problems: A Survey
• Complexity of k-SAT
• An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments
• Clique, Independent Set, and Vertex Cover
• Towards maximum independent sets on massive graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments
• A branch and bound algorithm for the maximum clique problem
• 3-coloring in time
• On Problems as Hard as CNFSAT
• A Bottom-Up Method and Fast Algorithms for max independent set
• Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs
• Exact algorithms for maximum independent set
• A measure & conquer approach for the analysis of exact algorithms
• Improved Parameterized Upper Bounds for Vertex Cover
• A note on the complexity of minimum dominating set
• On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms
• Finding Induced Subgraphs via Minimal Triangulations
• Clique problem [wikipedia]
• Independent set (graph theory) [wikipedia]