# Greedily Finding a Dense Subgraph

Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, Takeshi Tokuyama

149 被引用数 (Scopus)

## 抄録

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)2 - O(n-1/3) ≤ R ≤ (1/2 + n/2k)2 + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k - 1) - O(1/k) ≤ R ≤ 2(n/k - 1) + O(n/k2) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± 0(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.

本文言語 English 203-221 19 Journal of Algorithms 34 2 https://doi.org/10.1006/jagm.1999.1062 Published - 2000 2月 はい

• 制御と最適化
• 計算数学
• 計算理論と計算数学

## フィンガープリント

「Greedily Finding a Dense Subgraph」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。