Message Passing for Maximum Weight Independent Set
From MaRDI portal
Publication:4974041
DOI10.1109/TIT.2009.2030448zbMath1367.94443MaRDI QIDQ4974041
Devavrat Shah, Alan S. Willsky, Sujay Sanghavi
Publication date: 8 August 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Decoding (94B35)
Related Items (7)
Belief propagation for the maximum-weight independent set and minimum spanning tree problems ⋮ Convergence and Correctness of Max-Product Belief Propagation for Linear Programming ⋮ Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Algorithms for the generalized independent set problem based on a quadratic optimization approach ⋮ Speeding-up structured probabilistic inference using pattern mining
This page was built for publication: Message Passing for Maximum Weight Independent Set
