Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F23%3A00131740" target="_blank" >RIV/00216224:14310/23:00131740 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007/s00186-023-00835-y" target="_blank" >https://link.springer.com/article/10.1007/s00186-023-00835-y</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00186-023-00835-y" target="_blank" >10.1007/s00186-023-00835-y</a>
Alternative languages
Result language
angličtina
Original language name
Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem
Original language description
We consider a variant of the clustering problem for a complete weighted graph. The aim is to partition the nodes into clusters maximizing the sum of the edge weights within the clusters. This problem is known as the clique partitioning problem, being NP-hard in the general case of having edge weights of different signs. We propose a new method of estimating an upper bound of the objective function that we combine with the classical branch-and-bound technique to find the exact solution. We evaluate our approach on a broad range of random graphs and real-world networks. The proposed approach provided tighter upper bounds and achieved significant convergence speed improvements compared to known alternative methods.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10100 - Mathematics
Result continuities
Project
<a href="/en/project/EF16_019%2F0000822" target="_blank" >EF16_019/0000822: CyberSecurity, CyberCrime and Critical Information Infrastructures Center of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Mathematical Methods of Operations Research
ISSN
1432-2994
e-ISSN
1432-5217
Volume of the periodical
98
Issue of the periodical within the volume
2
Country of publishing house
DE - GERMANY
Number of pages
29
Pages from-to
269-297
UT code for WoS article
001061721300001
EID of the result in the Scopus database
2-s2.0-85170046506