Dense subgraph
id:
dense-subgraph-283-372165
title:
Dense subgraph
text:
In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = be an undirected graph and let S = 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
brand slug:
wiki
category slug:
encyclopedia
description:
Highly connected subgraph
original url:
https://en.wikipedia.org/wiki/Dense_subgraph
date created:
date modified:
2023-12-03T16:33:51Z
main entity:
{"identifier":"Q5259307","url":"https://www.wikidata.org/entity/Q5259307"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/a/ae/Dense_subgraph.png","width":371,"height":285}
fields total:
13
integrity:
15