About: Dense subgraph

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In graph theory and computer science, a dense subgraph is a subgraph with a high level of internal connectivity. 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:

thumbnail
Property Value
dbo:abstract
  • In graph theory and computer science, a dense subgraph is a subgraph with a high level of internal connectivity. 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. 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 to run in O(nm log(n2/m)) time. A simple LP for finding the optimal solution was given by Charikar in 2000. (en)
dbo:thumbnail
dbo:wikiPageID
  • 32498620 (xsd:integer)
dbo:wikiPageLength
  • 10067 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1096382154 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In graph theory and computer science, a dense subgraph is a subgraph with a high level of internal connectivity. 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: (en)
rdfs:label
  • Dense subgraph (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License