Mathematical Formulations for the Acyclic Partitioning Problem

Jenny Nossack () and Erwin Pesch ()
Additional contact information
Jenny Nossack: University of Siegen
Erwin Pesch: University of Siegen

A chapter in Operations Research Proceedings 2013, 2014, pp 333-339 from Springer

Abstract: Abstract This paper addresses the problem of partitioning the vertex set of a given directed, edge- and vertex-weighted graph into disjoint subsets (i.e., clusters). Clusters are to be determined such that the sum of the vertex weights within the clusters satisfies an upper bound and the sum of the edge weights within the clusters is maximized. Additionally, the digraph is enforced to partition into a directed, acyclic graph, i.e., a digraph that contains no directed cycle. This problem is known in the literature as acyclic partitioning problem and is proven to be NP-hard in the strong sense. Real-life applications arise, e.g., at rail-rail transshipment yards and in Very Large Scale Integration (VLSI) design. We propose two model formulations for the acyclic partitioning problem, a compact and an augmented set partitioning model.

Keywords: Acyclic Partition; Graph Partitioning Problem; Transshipment Yard; Vertex Weights; Partitioning Digraph (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-319-07001-8_45

Ordering information: This item can be ordered from
http://www.springer.com/9783319070018

DOI: 10.1007/978-3-319-07001-8_45

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().