Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
type: Item
instance of: scholarly article
title: Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
zbMATH Open document ID: 1387.05255
author: Michel Minoux
author: Viet Hung Nguyen
author: Thanh Hai Nguyen
author: Renaud Sirdey
author: Dang Phuong Nguyen
published in: Discrete Optimization
publication date: 2018-05-24T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 6872144
zbMATH Keywords: graph partitioning
zbMATH Keywords: triangle inequality
zbMATH Keywords: SONET/SDH network design
describes a project that uses: METIS
describes a project that uses: DIMACS
MaRDI profile type: Publication
full work available at URL: j.disopt.2016.05.003
OpenAlex ID: W2472377441
cites work: Q4198056
cites work: SONET/SDH ring assignment with capacity constraints
cites work: On the Solution of a Graph Partitioning Problem under Capacity Constraints
cites work: Facet-defining inequalities for the simple graph partitioning polytope
cites work: Size-constrained graph partitioning polytopes
cites work: The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts
cites work: The node capacitated graph partitioning problem: A computational study
cites work: Orbitopal fixing
cites work: On the cut polytope
cites work: A cutting plane algorithm for a clustering problem
cites work: The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
cites work: New approaches for optimizing over the semimetric polytope
cites work: Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
cites work: Graph Partitioning and Graph Clustering
cites work: L’algebre de Boole et ses applications en recherche operationnelle
DOI: 10.1016/J.DISOPT.2016.05.003
Recommended article: Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
Recommended article: Improved approximation algorithms for maximum graph partitioning problems
Recommended article: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Compact mathematical formulation for graph partitioning
Recommended article: A strong formulation for the graph partition problem
Recommended article: An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
Recommended article: Compact structure for sparse undirected graphs based on a clique graph partition
Recommended article: Algorithms for Partition of Some Class of Graphs under Compaction
Recommended article: Q3575418
Recommended article: On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
description: scientific article; zbMATH DE number 6872144