Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

DOI10.1007/s12532-022-00228-yzbMath1519.90124OpenAlexW4309305091MaRDI QIDQ6102859

Jose L. Walteros, Demetrios V. Papazaharias

Publication date: 23 June 2023

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

Full work available at URL: https://doi.org/10.1007/s12532-022-00228-y

zbMATH Keywords

integer programmingdynamic programminggraph partitioningbranch-and-cutcritical element detection

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Mixed integer programming (90C11) Deterministic network models in operations research (90B10)

Cites Work

• Minimum edge blocker dominating set problem
• Graph clustering
• Size-constrained graph partitioning polytopes
• A shifting algorithm for constrained min-max partition on trees
• Facets of the clique partitioning polytope
• Balanced graph partitioning
• Detecting critical nodes in sparse graphs
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• A cutting plane algorithm for a clustering problem
• The ellipsoid method and its consequences in combinatorial optimization
• The discipline number of a graph
• Cliques and clustering: A combinatorial approach
• The node capacitated graph partitioning problem: A computational study
• Min-cut clustering
• On the monotonization of polyhedra
• Compact vs. exponential-size LP relaxations
• Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
• \(b\)-tree facets for the simple graph partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A cutting plane algorithm for computing \(k\)-edge survivability of a network
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Political districting to minimize cut edges
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• A survey of network interdiction models and algorithms
• The partition problem
• Partitioning a weighted tree into subtrees with weights in a given range
• On generating maximal nondominated Benders cuts
• Facet-defining inequalities for the simple graph partitioning polytope
• Edmonds polytopes and a hierarchy of combinatorial problems
• New approaches for optimizing over the semimetric polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• Integer programming methods for solving binary interdiction games
• Statistical mechanics of complex networks
• BOULWARE STATE IN EXACTLY SOLVABLE MODELS OF 2D DILATON GRAVITY
• VLSI Physical Design: From Graph Partitioning to Timing Closure
• A Linear Tree Partitioning Algorithm
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• A simple min-cut algorithm
• The clique partitioning problem: Facets and patching facets
• Integer programming models for detecting graph bipartitions with structural requirements
• Detecting critical node structures on graphs: A mathematical programming approach
• Minimum vertex blocker clique problem
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Dominants and submissives of matching polyhedra
• Efficient Algorithm for the Partitioning of Trees
• Shortest-path network interdiction
• Imposing Contiguity Constraints in Political Districting Models
• Solving the Distance-Based Critical Node Problem
• Why Is Maximum Clique Often Easy in Practice?
• Collective dynamics of ‘small-world’ networks
• Disconnecting graphs by removing vertices: a polyhedral approach
• Integer Programming and Combinatorial Optimization
• Extended formulations in combinatorial optimization
• A simulated annealing approach to police district design
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations