In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = (V, E) be an undirected graph and let S = (VS, ES) be a subgraph of G. Then the density of S is defined to be:
The densest subgraph problem is that of finding a subgraph of maximum density. The density of the maximally dense subgraph of a graph is sometimes referred to as its subgraph density. In 1984, Andrew V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique. This has been improved by Gallo, Grigoriadis and Tarjan in 1989[1] to run in O(nm log(n2/m)) time. A simple LP for finding the optimal solution was given by Charikar in 2000.[2]
Subgraph density is asymptotic to the related notion of arboricity and to graph degeneracy.
- ^ Gallo, Giorgio; Grigoriadis, Michael D.; Tarjan, Robert E. (1989), "A fast parametric maximum flow algorithm and applications", SIAM Journal on Computing, 18 (1): 30–55, doi:10.1137/0218003, MR 0978165
- ^ Charikar, Moses (2000), "Greedy approximation algorithms for finding dense components in a graph", in Jansen, Klaus; Khuller, Samir (eds.), Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1913, Springer, pp. 84–95, doi:10.1007/3-540-44436-X_10, ISBN 978-3-540-67996-7