Independent sets in bounded-degree hypergraphs

DOI10.1016/J.DAM.2008.11.013zbMath1173.05035OpenAlexW2138024384MaRDI QIDQ1026137

Magnús M. Halldórsson, Elena Losievskaja

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.11.013

zbMATH Keywords

hypergraphapproximation algorithmsmaximum independent set

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Transversals and independence in linear hypergraphs with maximum degree two ⋮ Independent sets in semi-random hypergraphs ⋮ On vertex independence number of uniform hypergraphs ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ Zeon and idem-Clifford formulations of hypergraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Tight results on minimum entropy set cover
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• On approximation properties of the independent set problem for low degree graphs
• On the differential approximation of MIN SET COVER
• An analysis of the greedy algorithm for the submodular set covering problem
• A note on greedy algorithms for the maximum weighted independent set problem
• Approximating min sum set cover
• Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• A threshold of ln n for approximating set cover
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• A Greedy Heuristic for the Set-Covering Problem
• Improved lower bounds on k‐independence
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• k-Independence and thek-residue of a graph
• Non-approximability results for optimization problems on bounded degree instances
• Paths, Trees, and Flowers

This page was built for publication: Independent sets in bounded-degree hypergraphs