Independent sets in bounded-degree hypergraphs
From MaRDI portal
Publication:1026137
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
Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
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
