Message Passing for Maximum Weight Independent Set

DOI10.1109/TIT.2009.2030448MaRDI QIDQ4974041zbMATH OpenFDO

Authors Sujay Sanghavi, Devavrat Shah, Alan S. Willsky

Publication date 8 August 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TIT.2009.2030448

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Decoding (94B35)

Cited in

(9)

• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• A new distributed approximation algorithm for the maximum weight independent set problem
• Convergence and correctness of belief propagation for the Chinese postman problem
• Algorithms for the generalized independent set problem based on a quadratic optimization approach
• Speeding-up structured probabilistic inference using pattern mining
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming
• Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
• Belief propagation for unbalanced assignment problem
• Convergence and correctness of belief propagation for weighted min-max flow

This page was built for publication: Message Passing for Maximum Weight Independent Set

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