Finding a Maximum Independent Set

1977/09/01 by Robert E. Tarjan, Anthony E. Trojanowski · 21 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Independent set #Maximal independent set #Combinatorics #Vertex (graph theory) #Set (abstract data type) #Computer science #Graph #Mathematics #Dominating set #Algorithm #Chordal graph #1-planar graph

paper · doi:10.1137/0206038

openalex publication_date 1977/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present an algorithm which finds a maximum independent set in an n-vertex graph in O(2^n/3) time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.

Citations

• The complexity of theorem-proving procedures
• Computing Partitions with Applications to the Knapsack Problem
• 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
• Finding a Maximum Clique in an Arbitrary Graph
• An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments
• On the independent set problem in random 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
• Counting models for 2SAT and 3SAT formulae
• 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
• A note on the complexity of minimum dominating set
• Combinatorial bounds via measure and conquer
• Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture
• Finding Induced Subgraphs via Minimal Triangulations
• Circuit design for clique problem and its implementation on quantum computer
• Clique problem [wikipedia]