Parsimonious formulations for low-diameter clusters

DOI10.1007/s12532-020-00175-6zbMath1452.90083OpenAlexW3003314745MaRDI QIDQ2220903

Hosseinali Salemi, Austin Buchanan

Publication date: 25 January 2021

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-020-00175-6

zbMATH Keywords

clusterinteger programmingbounded diameter\(k\)-clubdistance constrainthop constraintlength-bounded cutlow-diameter

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Integer programming (90C10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ Solving the Distance-Based Critical Node Problem ⋮ A hybrid solution method for the bi-objective traffic counting location problem using previous origin-destination trip tables ⋮ 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 ⋮ Graph signatures: identification and optimization ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ Political districting to minimize cut edges

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for the maximum \(k\)-club problem in graphs
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Minimum degree orderings
• Using separation algorithms to generate mixed integer model reformulations
• Mengerian theorems for paths of bounded length
• Geometric algorithms and combinatorial optimization.
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Which problems have strongly exponential complexity?
• 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
• On imposing connectivity constraints in integer programs
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Heuristics for finding \(k\)-clubs in an undirected graph
• On clique relaxation models in network analysis
• An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem
• Fast algorithms for determining (generalized) core groups in social networks
• Novel approaches for analyzing biological networks
• Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
• Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• On the 2-Club Polytope of Graphs
• Length-bounded cuts and flows
• Smallest-last ordering and clustering and graph coloring algorithms
• A graph‐theoretic definition of a sociometric clique†
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Imposing Connectivity Constraints in Forest Planning Models
• Integer models and upper bounds for the 3‐club problem
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Max flows in O(nm) time, or better
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• On the complexity of \(k\)-SAT

This page was built for publication: Parsimonious formulations for low-diameter clusters