Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs

2012/10/17 by Mingyu Xiao, Hiroshi Nagamochi · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Bottleneck #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Degree (music) #Discrete mathematics #Graph #Independent set #Interconnection Networks and Systems #Mathematics #Running time #Set (abstract data type) #Simple (philosophy) #Upper and lower bounds #Vertex (graph theory)

paper · pdf · doi:10.1016/j.tcs.2012.09.022

openalex publication_date 2012/10/17 · crossref created 2012/10/17 · crossref issued 2013/01/01 · crossref published 2013/01/01 · crossref published-print 2013/01/01 · crossref deposited 2018/11/19 · openalex created_date 2025/10/10 · crossref indexed 2026/03/14 · openalex updated_date 2026/07/31

Citations

• A Bottom-Up Method and Fast Algorithms for max independent set
• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Pathwidth of cubic graphs and exact algorithms

Cited by

• Branch-and-Bound Tensor Networks for Exact Ground-State Characterization
• Exact algorithms for maximum independent set
• Independent set (graph theory) [wikipedia]