An exact algorithm for the minimum gap graph partitioning problem

DOI10.1016/J.COR.2025.107224MaRDI QIDQ6891485zbMATH OpenFDO

Authors Maurizio Bruglieri, Gianluca Consiglio, Roberto Cordone

Publication date 2 December 2025

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COR.2025.107224

zbMATH Keywords

graph partitioningset coveringbranch-and-boundLagrangian relaxationreduction procedures

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites work

• scientific article; zbMATH DE number 3894826 (Why is no real title available?)
• A Heuristic Method for the Set Covering Problem
• A Lagrangian-based heuristic for large-scale set covering problems
• Algorithms for the set covering problem
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Branch-and-price: Column generation for solving huge integer programs
• Cardinality constrained connected balanced partitions of trees under different criteria
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Graph partitioning: an updated survey
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Integrated versus hierarchical approach for zone delineation and crop planning under uncertainty
• Lagrangean relaxation. (With comments and rejoinder).
• Metaheuristics for the minimum gap graph partitioning problem
• On finding connected balanced partitions of trees
• On the mixed set covering, packing and partitioning polytope
• Partitioning a graph into minimum gap components
• Partitioning a weighted tree into subtrees with weights in a given range
• Partitioning graphs into balanced components

This page was built for publication: An exact algorithm for the minimum gap graph partitioning problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891485)