A New Branch and Bound Algorithm for the Clique Partitioning Problem

Jörg Rambau () and Cornelius Schwarz ()
Additional contact information
Jörg Rambau: University of Bayreuth
Cornelius Schwarz: University of Bayreuth

Chapter 74 in Operations Research Proceedings 2008, 2009, pp 457-462 from Springer

Abstract: Summary This paper considers the problem of clustering the vertices of a complete, edge weighted graph. The objective is to maximize the edge weights within the clusters (also called cliques). This so called Clique Partitioning Problem (CPP) is NP-complete, but it has several real life applications such as groupings in exible manufacturing systems, in biology, in flight gate assignment, etc.. Numerous heuristic and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from literature, improve constraint propagation techniques for fixing edges in each node, and present a new branching scheme

Keywords: Child Node; Edge Weight; Weighted Graph; Constraint Propagation; Benchmark Test (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

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:sprchp:978-3-642-00142-0_74

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

DOI: 10.1007/978-3-642-00142-0_74

Access Statistics for this chapter

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