Abstract
We study the problem of finding highly connected subgraphs of undirected and directed graphs. For undirected graphs, the notion of density of a subgraph we use is the average degree of the subgraph. For directed graphs, a corresponding notion of density was introduced recently by Kannan and Vinay. This is designed to quantify highly connectedness of substructures in a sparse directed graph such as the web graph. We study the optimization problems of finding subgraphs maximizing these notions of density for undirected and directed graphs. This paper gives simple greedy approximation algorithms for these optimization problems. We also answer an open question about the complexity of the optimization problem for directed graphs.
Research supported by the Pierre and Christine Lamond Fellowship, an ARO MURI Grant DAAH04-96-1-0007 and NSF Grant IIS-9811904. Part of this work was done while the author was visiting IBM Almaden Research Center.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Y. Asahiro and K. Iwama. Finding Dense Subgraphs. Proc. 6th International Symposium on Algorithms and Computation (ISAAC), LNCS 1004, 102–111 (1995).
Y. Asahiro, K. Iwama, H. Tamaki and T. Tokuyama. Greedily Finding a Dense Subgraph. Journal of Algorithms, 34(2):203–221 (2000).
P. Drineas, A. Frieze, R. Kannan, S. Vempala and V. Vinay. Clustering in Large Graphs and Matrices. Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 291–299 (1999).
U. Feige, G. Kortsarz and D. Peleg. The Dense k-Subgraph Problem. Algorithmica, to appear. Preliminary version in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, 692–701 (1993).
U. Feige and M. Seltser. On the Densest k-Subgraph Problem. Weizmann Institute Technical Report CS 97-16 (1997).
A. Frieze, R. Kannan and S. Vempala. Fast Monte-Carlo Algorithms for Finding Low Rank Approximations. Proc. 39th Annual IEEE Symposium on Foundations of Computer Science, 370–378 (1998).
G. Gallo, M. D. Grigoriadis, and R. Tarjan. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM J. on Comput., 18:30–55 (1989).
D. Gibson, J. Kleinberg and P. Raghavan. Inferring web communities from Web topology. Proc. HYPERTEXT, 225–234 (1998).
R. Kannan and V. Vinay. Analyzing the Structure of Large Graphs. manuscript, August 1999.
J. Kleinberg. Authoritative sources in hypertext linked environments. Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 668–677 (1998).
J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. The web as a graph: measurements, models, and methods. Proc. 5th Annual International Conference on Computing and Combinatorics (COCOON), 1–17 (1999).
S. R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Trawling Emerging Cyber-Communities Automatically. Proc. 8th WWW Conference, Computer Networks, 31(11-16):1481–1493, (1999).
13. E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Charikar, M. (2000). Greedy Approximation Algorithms for Finding Dense Components in a Graph. In: Jansen, K., Khuller, S. (eds) Approximation Algorithms for Combinatorial Optimization. APPROX 2000. Lecture Notes in Computer Science, vol 1913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44436-X_10
Download citation
DOI: https://doi.org/10.1007/3-540-44436-X_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67996-7
Online ISBN: 978-3-540-44436-7
eBook Packages: Springer Book Archive