A note on greedy algorithms for the maximum weighted independent set problem

By Shuichi Sakai, Mitsunori Togasaki, K. Yamazaki. Discrete Applied Mathematics, 2003

319 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/aca801b57d198d4a6946537e0b0f7d2706f6d5ee

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Ben Y. Zhao
2. Chunyi Peng
3. Haitao Zheng

In Discrete Mathematics and Combinatorics

1. Ben Y. Zhao
2. Chunyi Peng
3. Haitao Zheng

Citations in the corpus

• Utilization and fairness in spectrum assignment for opportunistic spectrum access (2006, methodology): “i bni ,mi (40) Actually, (40) obtains the generalization of Weighted Independent Set Problem in Color-Sensitive Graph Coloring Problem in [21].”
• eBay in the Sky: strategy-proof wireless spectrum auctions (2008, background): “For example, it has been shown that to maximize the sum of winning bids, also known as the social welfare [11], the best-known greedy allocation algorithm assigns channel following the descending order of bi |N(i)+1| [14].”