Prikl. Diskr. Mat., 2018, Number 42, Pages 66–75
This article is cited in 1 scientific paper (total in 1 paper)
Applied Graph Theory
On a semi-superwized graph clustering problem
A. V. Ilevab, V. P. Il'evac
a Omsk State Technical University, Omsk, Russia
b Sobolev Institute of Mathematics SB RAS, Omsk, Russia
c Dostoevsky Omsk State University, Omsk, Russia
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.
graph, cluster, semi-supervised clustering.
PDF file (679 kB)
A. V. Ilev, V. P. Il'ev, “On a semi-superwized graph clustering problem”, Prikl. Diskr. Mat., 2018, no. 42, 66–75
Citation in format AMSBIB
\by A.~V.~Ilev, V.~P.~Il'ev
\paper On a semi-superwized graph clustering problem
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. N. Rybalov, “O genericheskoi slozhnosti problemy klasterizatsii grafov”, PDM, 2019, no. 46, 72–77
|Number of views:|