Integer models and upper bounds for the 3‐club problem

DOI10.1002/net.21455zbMath1269.90120OpenAlexW2118929181MaRDI QIDQ5326766

Filipa D. Carvalho, Maria Teresa Almeida

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21455

zbMATH Keywords

computational biologysocial network analysisclique relaxationsinteger formulations\(k\)-clubdiameter constrained problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

The triangle \(k\)-club problem ⋮ Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ 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 ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ 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 ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ On structural parameterizations for the 2-club problem

Cites Work

• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Upper bounds and heuristics for the 2-club problem
• Selected combinatorial problems of computational biology
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• 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
• Extended and discretized formulations for the maximum clique problem
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
• A graph‐theoretic definition of a sociometric clique†
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
• Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion

This page was built for publication: Integer models and upper bounds for the 3‐club problem