Belief propagation for the maximum-weight independent set and minimum spanning tree problems
DOI10.1016/j.tcs.2018.04.046zbMath1395.90212OpenAlexW2802287231WikidataQ129901456 ScholiaQ129901456MaRDI QIDQ1643153
Kamiel Cornelissen, Bodo Manthey
Publication date: 18 June 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.04.046
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
- Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
- Proof of the Satisfiability Conjecture for Large k
- Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
- A Spectral Approach to Analysing Belief Propagation for 3-Colouring
- Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
- A rigorous analysis of the cavity equations for the minimum spanning tree
- Message Passing for Maximum Weight Independent Set
- Belief Propagation and LP Relaxation for Weighted Matching in General Graphs
This page was built for publication: Belief propagation for the maximum-weight independent set and minimum spanning tree problems
