4.3 Article

Top-k overlapping densest subgraphs: approximation algorithms and computational complexity

Related references

Note: Only part of the references are listed.
Article Computer Science, Interdisciplinary Applications

Top-k overlapping densest subgraphs: approximation algorithms and computational complexity

Riccardo Dondi et al.

Summary: The central problem in graph mining is the discovery of dense subgraphs, with a recent focus on finding a set of densest subgraphs. The Top-k-Overlapping Densest Subgraphs problem aims to find a set of k dense subgraphs that may share vertices, with an objective function considering density, parameter lambda, and distance. Research has shown a 1/10-factor approximation algorithm for this problem, while also proving its NP-hardness.

JOURNAL OF COMBINATORIAL OPTIMIZATION (2021)

Article Computer Science, Software Engineering

The Densest Subgraph Problem with a Convex/Concave Size Function

Yasushi Kawase et al.

ALGORITHMICA (2018)

Article Computer Science, Software Engineering

Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

Yuichi Asahiro et al.

ALGORITHMICA (2018)

Proceedings Paper Computer Science, Information Systems

Fully Dynamic Algorithm for Top-k Densest Subgraphs

Muhammad Anis Uddin Nasir et al.

CIKM'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT (2017)

Article Computer Science, Artificial Intelligence

Top-k overlapping densest subgraphs

Esther Galbrun et al.

DATA MINING AND KNOWLEDGE DISCOVERY (2016)

Article Computer Science, Artificial Intelligence

Multivariate Algorithmics for Finding Cohesive Subnetworks

Christian Komusiewicz

ALGORITHMS (2016)

Proceedings Paper Computer Science, Artificial Intelligence

Finding Subgraphs with Maximum Total Density and Limited Overlap

Oana Denisa Balalau et al.

WSDM'15: PROCEEDINGS OF THE EIGHTH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING (2015)

Article Biochemical Research Methods

MotifCut: regulatory motifs finding with maximum density subgraphs

Eugene Fratkin et al.

BIOINFORMATICS (2006)

Article Mathematics, Applied

Complexity of finding dense subgraphs

Y Asahiro et al.

DISCRETE APPLIED MATHEMATICS (2002)

Article Management

An exact algorithm for the maximum k-club problem in an undirected graph

JM Bourjolly et al.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (2002)

Article Computer Science, Software Engineering

The dense k-subgraph problem

U Feige et al.

ALGORITHMICA (2001)