SDP-based algorithms for maximum independent set problems on hypergraphs

DOI10.1016/J.TCS.2012.11.025MaRDI QIDQ1935808zbMATH OpenOpenAlexFDO

Authors Geir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja

Publication date 19 February 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.390.361

zbMATH Keywords

approximation algorithmshypergraphsindependent sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
• Independent Sets in Bounded-Degree Hypergraphs
• Independent sets in bounded-degree hypergraphs
• scientific article; zbMATH DE number 1445320
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs

Cited in

(10)

• Independent sets in bounded-degree hypergraphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
• On vertex independence number of uniform hypergraphs
• scientific article; zbMATH DE number 3893238 (Why is no real title available?)
• Approximating independent sets in sparse graphs
• Automated category tree construction: hardness bounds and algorithms
• The low-degree hardness of finding large independent sets in sparse random hypergraphs

This page was built for publication: SDP-based algorithms for maximum independent set problems on hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1935808)