The Densest Subgraph Problem requires us to find, in a given graph, a subset of vertices
whose induced subgraph maximizes a measure of density. The problem has received a …

The maximum clique problem (MCP) is to determine in a graph a clique (ie, a complete
subgraph) of maximum cardinality. The MCP is notable for its capability of modeling other …

As one of the most fundamental problems in graph data mining, the densest subgraph
discovery (DSD) problem has found a broad spectrum of real applications, such as social …

As a fundamental problem in graph data mining, Densest Subgraph Discovery (DSD) aims
to find the subgraph with the highest density from a graph. It has been studied for several …

With the prevalence of graphs for modeling complex relationships among objects, the topic
of graph mining has attracted a great deal of attention from both academic and industrial …

In this paper, we consider the problem of maximizing the spread of influence through a
social network. Given a graph with a threshold value thr (v) attached to each vertex v, the …

We investigate the computational complexity of the Densest k-Subgraph problem, where the
input is an undirected graph G=(V, E) and one wants to find a subgraph on exactly k vertices …

Given a simple undirected graph G, a quasi-clique is a subgraph of G whose density is at
least γ (0< γ≤ 1). Finding a maximum quasi-clique has been addressed from two different …

Many graph concepts such as cliques, k-clubs, and k-plexes are used to define cohesive
subgroups in a social network. The concept of densest k-set is one of them. A densest k-set …

We study the parameterized complexity of a broad class of problems called “local graph
partitioning problems” that includes the classical fixed cardinality problems as max k k-vertex …