Independent Sets in Bounded-Degree Hypergraphs

DOI10.1007/978-3-540-73951-7_24MaRDI QIDQ3603532zbMATH OpenOpenAlexFDO

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

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_24

Mathematics Subject Classification ID

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

Recommendations

• Independent sets in bounded-degree hypergraphs
• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 1003268
• Improved approximations of independent sets in bounded-degree graphs
• SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs

Cited in

(15)

• Independent sets in bounded-degree hypergraphs
• Lower bounds for constant degree independent sets
• On the number of independent sets in simple hypergraphs
• SDP-based algorithms for maximum independent set problems on hypergraphs
• Locally defined independence systems on graphs
• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent
• scientific article; zbMATH DE number 5901714 (Why is no real title available?)
• SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
• Independent Sets in Regular Hypergraphs and Multidimensional Runlength-Limited Constraints
• Hypergraph Independent Sets
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• Differential Methods for Finding Independent Sets in Hypergraphs
• A better differential approximation ratio for symmetric TSP
• New differential approximation algorithm for \(k\)-customer vehicle routing problem

This page was built for publication: Independent Sets in Bounded-Degree Hypergraphs

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