This article is cited in 3 papers

Applied Graph Theory

On a semi-superwized graph clustering problem

A. V. Ilev^ab, V. P. Il'ev<sup>ac

a</sup> Omsk State Technical University, Omsk, Russia
^b Sobolev Institute of Mathematics SB RAS, Omsk, Russia
^c Dostoevsky Omsk State University, Omsk, Russia

Abstract: In the clustering problems one has to partition a given set of objects into some subsets (called clusters) taking into consideration only similarity of the objects. In this paper we study a version of the graph correlation clustering that can be considered as a formalization of the semi-supervised clustering. We prove that the problem under consideration is NP-hard and propose a polynomial-time 3-approximation algorithm for a version of the problem.

Keywords: graph, cluster, semi-supervised clustering.

UDC: 519.1

DOI: 10.17223/20710410/42/5

Bibliographic databases:

• 
•