An O(20.304n) Algorithm for Solving Maximum Independent Set Problem

1986/09/01 by Jian Tang · 11 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #Algorithm #Computer science #Set (abstract data type) #Independent set #Graph #Mathematics #Combinatorics

paper · doi:10.1109/tc.1986.1676847

openalex publication_date 1986/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07

Abstract

A faster algorithm for finding a maximum independent set in a graph is presented. The algorithm is an improved version of the one by Tarjan and Trojanowski [7]. A technique to further accelerate this algorithm is also described.

Citations

• Algorithm 457: finding all cliques of an undirected graph

Cited by

• Exact Algorithms for NP-Hard Problems: A Survey
• Complexity of k-SAT
• On the independent set problem in random graphs
• Clique, Independent Set, and Vertex Cover
• 3-coloring in time
• 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
• A note on the complexity of minimum dominating set
• Finding Induced Subgraphs via Minimal Triangulations
• Clique problem [wikipedia]