A local algorithm for finding dense subgraphs

DOI10.1145/1824777.1824780zbMATH Open1300.05293arXivcs/0702078OpenAlexW2620706275MaRDI QIDQ2930342FDOQ2930342

Authors: Reid Andersen 

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: We 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.

Full work available at URL: https://arxiv.org/abs/cs/0702078

Recommendations

• A local algorithm for finding dense bipartite-like subgraphs
• On Finding Dense Subgraphs
• Algorithms and Computation
• Dense subgraph problems with output-density conditions
• Finding Dense Subgraphs with Size Bounds

zbMATH Keywords

spectral graph theorylocal algorithmsdense subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (3)

• On the probe complexity of local computation algorithms
• Chromatic kernel and its applications
• A local algorithm for finding dense bipartite-like subgraphs

This page was built for publication: A local algorithm for finding dense subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930342)