Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
From MaRDI portal
Publication:1751240
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
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
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