On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs

DOI10.1016/j.disopt.2012.02.002zbMath1246.90130OpenAlexW2045574977MaRDI QIDQ448967

Balabhaskar Balasundaram, Foad Mahdavi Pajouh

Publication date: 11 September 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.02.002

zbMATH Keywords

cliquesocial network analysisgraph-based data mining\(k\)-clubsexact combinatorial algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Combinatorial optimization (90C27)

Related Items

The triangle \(k\)-club problem, Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts, Optimal approximation algorithms for maximum distance-bounded subgraph problems, Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights, Finding disjoint dense clubs in a social network, On Fault-Tolerant Low-Diameter Clusters in Graphs, Two-phase heuristics for the \(k\)-club problem, Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems, Integer models and upper bounds for the 3‐club problem, A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques, Algorithms for the maximum \(k\)-club problem in graphs, Finding clubs in graph classes, On maximum ratio clique relaxations, On the 2-Club Polytope of Graphs, On biconnected and fragile subgraphs of low diameter, On computing large temporal (unilateral) connected components, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Parsimonious formulations for low-diameter clusters, Finding Disjoint Dense Clubs in an Undirected Graph, Finding large \(k\)-clubs in undirected graphs, Graph signatures: identification and optimization, Detecting large risk-averse 2-clubs in graphs with random edge failures, An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem, The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms, Finding clique clusters with the highest betweenness centrality, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, Exact algorithms for the minimum \(s\)-club partitioning problem, On structural parameterizations for the 2-club problem

Uses Software

• Ucinet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Upper bounds and heuristics for the 2-club problem
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• An exact algorithm for the maximum clique problem
• Clustering and domination in perfect graphs
• On approximating the maximum diameter ratio of graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• A fast algorithm for the maximum clique problem
• Heuristics for finding \(k\)-clubs in an undirected graph
• Clique-detection models in computational biochemistry and genomics
• Mining market data: a network approach
• Novel approaches for analyzing biological networks
• Approximating Maximum Diameter-Bounded Subgraphs
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• A graph‐theoretic definition of a sociometric clique†
• A graph‐theoretic generalization of the clique concept
• New methods to color the vertices of a graph
• Heuristic and Special Case Algorithms for Dispersion Problems
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• Node-and edge-deletion NP-complete problems