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

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

Recommendations

• SDP-based algorithms for maximum independent set problems on hypergraphs
• Independent Sets in Bounded-Degree Hypergraphs
• Independent sets in bounded-degree hypergraphs
• Publication:4952635
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs

Cited in

(7)

• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Independent sets in bounded-degree hypergraphs
• On vertex independence number of uniform hypergraphs
• Independent Sets in Bounded-Degree Hypergraphs
• SDP-based algorithms for maximum independent set problems on hypergraphs
• Approximating independent sets in sparse graphs
• scientific article; zbMATH DE number 3893238 (Why is no real title available?)

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)