Algorithms for the maximum \(k\)-club problem in graphs

DOI10.1007/s10878-012-9473-zzbMath1282.90220OpenAlexW2077064858MaRDI QIDQ385488

Shahram Shahinpour, Sergiy I. Butenko

Publication date: 2 December 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9473-z

zbMATH Keywords

variable neighborhood searchclique relaxationsmaximum \(k\)-club

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (12)

Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ On the 2-Club Polytope of Graphs ⋮ On biconnected and fragile subgraphs of low diameter ⋮ Parsimonious formulations for low-diameter clusters ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ On the maximum small-world subgraph problem ⋮ Exact algorithms for the minimum \(s\)-club partitioning problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Upper bounds and heuristics for the 2-club problem
• Variable neighborhood search for the maximum clique
• An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
• Local search and suffix tree for car-sequencing problem with colors
• Variable neighborhood search
• A variable neighborhood search for graph coloring.
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• A fast algorithm for the maximum clique problem
• Parameterized computational complexity of finding small-diameter subgraphs
• The parallel variable neighborhood search for the \(p\)-median problem
• Heuristics for finding \(k\)-clubs in an undirected graph
• Neighborhood structures for the container loading problem: a VNS implementation
• Solving the maximum clique problem using a tabu search approach
• Novel approaches for analyzing biological networks
• New methods to color the vertices of a graph
• Integer models and upper bounds for the 3‐club problem
• Handbook of metaheuristics
• Variable neighborhood search: Principles and applications

This page was built for publication: Algorithms for the maximum \(k\)-club problem in graphs