Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
From MaRDI portal
Publication:439496
DOI10.1016/j.ejor.2011.10.027zbMath1244.90201OpenAlexW2016182558MaRDI QIDQ439496
Alexander Veremyev, Vladimir L. Boginski
Publication date: 16 August 2012
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2011.10.027
combinatorial optimizationgraph theory\(k\)-clubs\(R\)-robust \(k\)-clubscompact \(0\)-\(1\) formulationsrobust network clusters
Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27)
Related Items (40)
The triangle \(k\)-club problem ⋮ Finding maximum subgraphs with relatively large vertex connectivity ⋮ Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Correction to: ``Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Approximating 2-cliques in unit disk graphs ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ Robustness and Strong Attack Tolerance of Low-Diameter Networks ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ On the number of edges in a graph with many two-hop disjoint paths ⋮ On the 2-Club Polytope of Graphs ⋮ On biconnected and fragile subgraphs of low diameter ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Parsimonious formulations for low-diameter clusters ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ On robust clusters of minimum cardinality in networks ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem ⋮ Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ On the maximum small-world subgraph problem ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ New analytical lower bounds on the clique number of a graph ⋮ Finding groups with maximum betweenness centrality ⋮ Trade-offs among degree, diameter, and number of paths ⋮ Variable neighborhood search for minimum sum-of-squares clustering on networks ⋮ On connected dominating sets of restricted diameter
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new linearization technique for multi-quadratic 0-1 programming problems.
- A note on a global approach for general 0-1 fractional programming
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- On the maximum quasi-clique problem
- Heuristics for finding \(k\)-clubs in an undirected graph
- Solving the maximum clique problem using a tabu search approach
- Linear forms of nonlinear expressions: new insights on old ideas
- Novel approaches for analyzing biological networks
- A Random Graph Model for Power Law Graphs
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- A graph‐theoretic generalization of the clique concept
- The Spectra of Random Graphs with Given Expected Degrees
- Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
This page was built for publication: Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
