The dense k-subgraph problem

被引：336

作者：

Feige, U ^{[1
]}

Kortsarz, G

Peleg, D

机构：

[1] Weizmann Inst, Dept Appl Math & Comp Sci, IL-76100 Rehovot, Israel

[2] Open Univ, Dept Comp Sci, Tel Aviv, Israel

来源：

ALGORITHMICA | 2001年 / 29卷 / 03期

关键词：

approximation algorithms; dense subgraph;

D O I：

10.1007/s004530010050

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O (n(delta)), for some delta < 1/3.

引用

页码：410 / 421

页数：12

共 11 条

[1] DERANDOMIZED GRAPH PRODUCTS
ALON, N
FEIGE, U
WIGDERSON, A
ZUCKERMAN, D
[J]. COMPUTATIONAL COMPLEXITY, 1995, 5 (01) : 60 - 75
[2] [Anonymous], 1996, LNCS
[3] Arora S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P284, DOI 10.1145/225058.225140
[4] BIGGS N, 1993, ALGEBRAIC GRAPH THER
[5] Feige U., 1997, CS9716 WEIZM I
[6] A FAST PARAMETRIC MAXIMUM FLOW ALGORITHM AND APPLICATIONS
GALLO, G
GRIGORIADIS, MD
TARJAN, RE
[J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (01) : 30 - 55
[7] Approximation algorithms for maximum dispersion
Hassin, R
Rubinstein, S
Tamir, A
[J]. OPERATIONS RESEARCH LETTERS, 1997, 21 (03) : 133 - 137
[8] Lawler E., 1976, Combinatorial Optimization: Networks and Matroids
[9] LEIGHTON FT, 1988, P 29 ANN IEEE S FDN, P422
[10] Marcus M., 1964, A Survey of Matrix Theory and Matrix Inequalities

← 1 2 →