A Local Algorithm for Finding Dense Subgraphs

Simple item page
dc.creatorAndersen, Reid
dc.date2007-02-13
dc.date.accessioned2026-07-07T07:46:47Z
dc.date.available2026-07-07T07:46:47Z
dc.descriptionWe present a local algorithm for finding dense subgraphs of bipartite graphs, according to the definition of density proposed by Kannan and Vinay. Our algorithm takes as input a bipartite graph with a specified starting vertex, and attempts to find a dense subgraph near that vertex. We prove that for any subgraph S with k vertices and density theta, there are a significant number of starting vertices within S for which our algorithm produces a subgraph S' with density theta / O(log n) on at most O(D k^2) vertices, where D is the maximum degree. The running time of the algorithm is O(D k^2), independent of the number of vertices in the graph.
dc.description14 pages, no figures
dc.identifierhttps://arxiv.org/abs/cs/0702078
dc.identifierhttp://arxiv.org/abs/cs/0702078
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/123946
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.subjectF.2.2; G.2.2
dc.titleA Local Algorithm for Finding Dense Subgraphs
dc.typetext

Files

Collections

arXiv