SDP-based algorithms for maximum independent set problems on hypergraphs

DOI10.1016/j.tcs.2012.11.025zbMath1258.05089OpenAlexW1964720370MaRDI QIDQ1935808

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

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

hypergraphsindependent setsapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (2)

On vertex independence number of uniform hypergraphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket

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