2008年8月
Dense Subgraph Problems with Output-Density Conditions
ACM TRANSACTIONS ON ALGORITHMS
ダウンロード
回数 : 109
- ,
- 巻
- 4
- 号
- 4
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1145/1383369.1383374
- 出版者・発行元
- ASSOC COMPUTING MACHINERY
We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized PTAS, even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o(n) vertices.
- リンク情報
- ID情報
-
- DOI : 10.1145/1383369.1383374
- ISSN : 1549-6325
- Web of Science ID : WOS:000265882200005