Approximating maximum independent sets by excluding subgraphs

DOI10.1007/3-540-52846-6_74zbMath1502.68212OpenAlexW1894405232MaRDI QIDQ5056088

Ravi B. Boppana, Magnús M. Halldórsson

Publication date: 9 December 2022

Published in: SWAT 90 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-52846-6_74

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Hard graphs for randomized subgraph exclusion algorithms, MNP: A class of NP optimization problems, A generalization of maximal independent sets, Independent set of intersection graphs of convex objects in 2D, On approximating the longest path in a graph

Cites Work

• Ramsey numbers and an approximation algorithm for the vertex cover problem
• A better performance guarantee for approximate graph coloring
• A note on Ramsey numbers
• Geometric algorithms and combinatorial optimization
• Approximation algorithms for combinatorial problems
• Improving the performance guarantee for approximate graph coloring
• Determining the Stability Number of a Graph
• On the Shannon capacity of a graph
• On the complexity of approximating the independent set problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item