Approximating maximum independent sets by excluding subgraphs

1992/06/01 by Ravi B. Boppana, Ravi Boppana, Magnús M. Halldórsson · 10 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Chordal graph #Clique #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Cover (algebra) #Discrete mathematics #Graph #Independent set #Mathematics #Optimization and Search Problems #Set (abstract data type) #Split graph #Vertex (graph theory) #Vertex cover

paper · doi:10.1007/bf01994876

crossref issued 1992/06/01 · crossref published 1992/06/01 · crossref published-print 1992/06/01 · openalex publication_date 1992/06/01 · crossref created 2005/08/04 · crossref deposited 2025/01/03 · openalex created_date 2025/10/10 · crossref indexed 2026/06/16 · openalex updated_date 2026/07/28

Citations

• A Combinatorial Problem in Geometry
• A note on Ramsey numbers
• Approximating clique is almost NP-complete

Cited by

• Probabilistic checking of proofs
• On the independent set problem in random graphs
• Clique is hard to approximate within n1−ε
• Approximating Maximum Clique by Removing Subgraphs
• A still better performance guarantee for approximate graph coloring
• On approximability of linear ordering and related NP-optimization problems on graphs
• The third open answer set programming competition
• Clique is hard to approximate within n/sup 1-ε/
• Clique problem [wikipedia]
• Triangle-free graph [wikipedia]