b-Tree Facets for the Simple Graph Partitioning Polytope

Michael M. Sørensen
Additional contact information
Michael M. Sørensen: The Aarhus School of Business

Journal of Combinatorial Optimization, 2004, vol. 8, issue 2, No 5, 170 pages

Abstract: Abstract The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each consisting of no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we introduce a large class of facet defining inequalities for the simple graph partitioning polytopes $$\mathcal{P}$$ n (b), b ≥ 3, associated with the complete graph on n nodes. These inequalities are induced by a graph configuration which is built upon trees of cardinality b. We provide a closed-form theorem that states all necessary and sufficient conditions for the facet defining property of the inequalities.

Keywords: clustering; graph partitioning; multicuts; polyhedral combinatorics (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/B:JOCO.0000031417.96218.26 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:2:d:10.1023_b:joco.0000031417.96218.26

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/B:JOCO.0000031417.96218.26

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().