The dense k-subgraph problem

被引：348

作者：

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 [J].

ALON, N ;

FEIGE, U ;

WIGDERSON, A ;

ZUCKERMAN, D .

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 [J].

GALLO, G ;

GRIGORIADIS, MD ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :30-55

[7] Approximation algorithms for maximum dispersion [J].

Hassin, R ;

Rubinstein, S ;

Tamir, A .

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 →