Email this article Graph clustering with a constraint on cluster sizes
- Authors: Il’ev V.P.1,2, Il’eva S.D.2, Navrotskaya A.A.1,2
-
Affiliations:
- Sobolev Institute of Mathematics
- Dostoevsky Omsk State University
- Issue: Vol 10, No 3 (2016)
- Pages: 341-348
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212403
- DOI: https://doi.org/10.1134/S1990478916030042
- ID: 212403
Cite item
Open Access
Access granted
Subscription Access
Abstract
A graph clustering problem is under study (also known as the graph approximation problem) with a constraint on cluster sizes. Some new approximation algorithm is presented for this problem, and performance guarantee of the algorithm is obtained. It is shown that the problem belongs to the class APX for every fixed p, where p is the upper bound on the cluster sizes.
About the authors
V. P. Il’ev
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Author for correspondence.
Email: iljev@mail.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
S. D. Il’eva
Dostoevsky Omsk State University
Email: iljev@mail.ru
Russian Federation, pr. Mira 55-A, Omsk, 644077
A. A. Navrotskaya
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Email: iljev@mail.ru
Russian Federation, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
Supplementary files
