A branch-and-bound algorithm for the acyclic partitioning problem

DOI10.1016/J.COR.2013.08.013MaRDI QIDQ336782zbMATH OpenOpenAlexFDO

Authors Jenny Nossack, Erwin Pesch

Publication date 10 November 2016

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

Full work available at URL https://doi.org/10.1016/j.cor.2013.08.013

zbMATH Keywords

graph partitioningacyclic graphbranch-and-boundconstraint propagationcontainer transshipment

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• An exact approach for the multi-constraint graph partitioning problem
• Computational study of a branching algorithm for the maximum \(k\)-cut problem
• scientific article; zbMATH DE number 1974111
• New bounds and constraint propagation techniques for the clique partitioning problem
• scientific article; zbMATH DE number 3997175

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A cutting plane algorithm for a clustering problem
• An Automatic Method of Solving Discrete Programming Problems
• An Efficient Heuristic Procedure for Partitioning Graphs
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• Cliques and clustering: A combinatorial approach
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and applications.
• Depth-First Search and Linear Graph Algorithms
• Efficient Algorithm for the Partitioning of Trees
• Facets of the clique partitioning polytope
• Fast Clustering Algorithms
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Handbook of Graph Theory
• Integer Programming Formulation of Traveling Salesman Problems
• Min-cut clustering
• Multiple-way network partitioning
• Network flows. Theory, algorithms, and applications.
• New bounds and constraint propagation techniques for the clique partitioning problem
• Optimal Sequential Partitions of Graphs
• Recent directions in netlist partitioning: a survey
• The clique partitioning problem: Facets and patching facets
• The node capacitated graph partitioning problem: A computational study
• The optimal graph partitioning problem. Solution method based on reducing symmetric nature and combinatorial cuts

Cited in

(4)

• Multilevel algorithms for acyclic partitioning of directed acyclic graphs
• scientific article; zbMATH DE number 3997175 (Why is no real title available?)
• Solving graph partitioning problems arising in tagless cache management
• Reformulated acyclic partitioning for rail-rail containers transshipment

This page was built for publication: A branch-and-bound algorithm for the acyclic partitioning problem

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