|
This article is cited in 5 scientific papers (total in 5 papers)
Graph clustering with a constraint on cluster sizes
V. P. Il'evab, S. D. Il'evab, A. A. Navrotskayaab a Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Omsk State University, 55-A Mir Ave., 644077 Omsk, Russia
Abstract:
A graph clustering problem (also known as the graph approximation problem) with a constraint on cluster sizes is studied. A new approximation algorithm is presented for this problem and performance guarantee of this algorithm is obtained. It is shown that the problem belongs to class $APX$ for every fixed $p$, where $p$ is the upper bound on the cluster sizes. Ill. 2, bibliogr. 20.
Keywords:
clustering, approximation, graph, approximation algorithm, performance guarantee.
Received: 28.12.2015 Revised: 28.03.2016
Citation:
V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Graph clustering with a constraint on cluster sizes”, Diskretn. Anal. Issled. Oper., 23:3 (2016), 5–20; J. Appl. Industr. Math., 10:3 (2016), 341–348
Linking options:
https://www.mathnet.ru/eng/da849 https://www.mathnet.ru/eng/da/v23/i3/p5
|
Statistics & downloads: |
Abstract page: | 244 | Full-text PDF : | 177 | References: | 29 | First page: | 3 |
|