density of a graph - the edge-density of a graph is the ratio of the number of edges vs the number of nodes
Highest Density Subgraph of a Graph
Problem
given a graph, find a subgraph with maximum edge-density
Methods in Solving this Problem
- this problem can be reduced to bipartite matching (which, in turn, is reducible to maximum flow)
- some other ways