Densest subgraph 密集子图

sublinear algorithm

Input:

Graph $G$. $V(G)$=set of nodes. $E(G)$ =set of edges

Def:

• $\forall U\in V(G)$
• $G_U$ = subgraph induced by U

• Density $d(G_U)=\frac{

  E(G_U)

  }{V(G_U)}$

• $d^{\ast }(G)=\underset{U\subseteq V}{max}d(G_U)$ Output:
• (Exact ) $d^{\ast }G(G)$
• (k-approx) $d’ s.t. \frac{d^G(G)}{k} \leq d’ \leq d^G(G)$

Some people call this (1/k)-approximation

找到一个子图，该子图的密度是图 $G$ 所有子图的密度中最大的。

k-approx：找到一个子图的密度满足在最大密度和 k 分之最大密度之间

#待整理笔记