A new distributed approximation algorithm for the maximum weight independent set problem

DOI10.1155/2016/9790629zbMath1400.90257OpenAlexW2515774600WikidataQ59141340 ScholiaQ59141340MaRDI QIDQ1793873

Yuan Zhang, Peng Du

Publication date: 12 October 2018

Published in: Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2016/9790629

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

Exploring further advantages in an alternative formulation for the set covering problem

Cites Work

• Unnamed Item
• Distributed algorithms for weighted problems in sparse graphs
• An optimal time algorithm for finding a maximum weight independent set in a tree
• On maximal independent sets of vertices in claw-free graphs
• Geometric algorithms and combinatorial optimization.
• A fast algorithm for the maximum weight clique problem
• A fast algorithm for the maximum clique problem
• A note on greedy algorithms for the maximum weighted independent set problem
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Factor graphs and the sum-product algorithm
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Message Passing for Maximum Weight Independent Set
• Arbitrary Throughput Versus Complexity Tradeoffs in Wireless Networks Using Graph Partitioning
• Optimized Scheduled Multiple Access Control for Wireless Sensor Networks
• Algorithms and Computation
• Belief Propagation and LP Relaxation for Weighted Matching in General Graphs
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Branching and Treewidth Based Exact Algorithms
• Graph-Theoretic Concepts in Computer Science
• Finding a maximal weighted independent set in wireless networks

This page was built for publication: A new distributed approximation algorithm for the maximum weight independent set problem