SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs

DOI10.1007/978-3-642-02927-1_3MaRDI QIDQ3638020zbMATH OpenOpenAlexFDO

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

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02927-1_3

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

(7)

• Independent sets in bounded-degree hypergraphs
• SDP-based algorithms for maximum independent set problems on hypergraphs
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Independent Sets in Bounded-Degree 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

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 Q3638020)