2014/03/20 by Andreas Wotzlaw, Wotzlaw, Andreas
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.DS #cs.LO
paper · pdf · doi:10.48550/arxiv.1403.5111
openalex publication_date 2014/03/20 · arxiv created 2014/04/03 · arxiv updated 2014/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a simple undirected graph G, the maximum k-club problem is to find a maximum-cardinality subset of nodes inducing a subgraph of diameter at most k in G. This NP-hard generalization of clique, originally introduced to model low diameter clusters in social networks, is of interest in network-based data mining and clustering applications. We give two MAX-SAT formulations of the problem and show that two exact methods resulting from our encodings outperform significantly the state-of-the-art exact methods when evaluated both on sparse and dense random graphs as well as on diverse real-life graphs from the literature.