Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem

Kód výsledku v IS VaVaI

RIV/00216224:14310/23:00131740 - isvavai.cz

Výsledek na webu

https://link.springer.com/article/10.1007/s00186-023-00835-y

DOI - Digital Object Identifier

10.1007/s00186-023-00835-y

Jazyk výsledku

angličtina

Název v původním jazyce

Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

EF16_019/0000822: Centrum excelence pro kyberkriminalitu, kyberbezpečnost a ochranu kritických informačních infrastruktur

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Mathematical Methods of Operations Research

ISSN

1432-2994

e-ISSN

1432-5217

Svazek periodika

98

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

29

Strana od-do

269-297

Kód UT WoS článku

001061721300001

EID výsledku v databázi Scopus

2-s2.0-85170046506