Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

DOI10.1016/j.disopt.2016.05.003zbMath1387.05255OpenAlexW2472377441MaRDI QIDQ1751240

Thanh Hai Nguyen, Viet Hung Nguyen, Renaud Sirdey, Michel Minoux, Dang-Phuong-Lan Nguyen

Publication date: 24 May 2018

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

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

zbMATH Keywords

graph partitioningtriangle inequalitySONET/SDH network design

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment ⋮ Stochastic graph partitioning: quadratic versus SOCP formulations ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

Uses Software

• METIS
• DIMACS

Cites Work

• Unnamed Item
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Orbitopal fixing
• Size-constrained graph partitioning polytopes
• A cutting plane algorithm for a clustering problem
• The node capacitated graph partitioning problem: A computational study
• SONET/SDH ring assignment with capacity constraints
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts
• Facet-defining inequalities for the simple graph partitioning polytope
• New approaches for optimizing over the semimetric polytope
• On the Solution of a Graph Partitioning Problem under Capacity Constraints
• L’algebre de Boole et ses applications en recherche operationnelle
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• On the cut polytope
• Graph Partitioning and Graph Clustering

This page was built for publication: Improved compact formulations for a wide class of graph partitioning problems in sparse graphs