scientific article; zbMATH DE number 17641
[For the entire collection see Zbl 0726.00015.] Given an undirected graph \(G=(V,E)\), a multicut is the set of edges connecting two different clusters of some partition of \(V\). The order of a multicut is the number of corresponding clusters. A multicut is \(s\)- balanced if different clusters have cardinalities differing by at most \(s\). A multicut polyhedron of \(G\) is the convex hull in \(R^ E\) of the incidence vectors of the multicuts of \(G\) with some particular property. In this paper these polyhedra are studied for following properties: all \(s\)-balanced multicuts, those of order at most (resp. at least or equal to) \(k\), and this for any \(s\). The aim is to describe families of facet generating inequalities. The main part of the text consists of a complete enumeration of the facets of all these polyhedra for the complete graph on 5 vertices. This leads to the determination of several families of facets for the multicut polyhedra of higher order complete graphs. The paper ends with a similar, but much simpler, complete description for the complete 4-graphs.
- Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
- Projection results for the \(k\)-partition problem
- Complete linear descriptions of small asymmetric traveling salesman polytopes
- Exploiting sparsity for the min \(k\)-partition problem
- A polyhedral study of lifted multicuts
- Clique-Web Facets for Multicut Polytopes
- A Note on Clique-Web Facets for Multicut Polytopes
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- On the dominant of the multicut polytope
- The inequicut cone
- The even and odd cut polytopes
- Chorded cycle facets of the clique partitioning polytope
- New bounds for the -k-cut and chromatic number of a graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974969)
