Отправить статью по E-mail Graph clustering with a constraint on cluster sizes
- Авторы: Il’ev V.1,2, Il’eva S.2, Navrotskaya A.1,2
-
Учреждения:
- Sobolev Institute of Mathematics
- Dostoevsky Omsk State University
- Выпуск: Том 10, № 3 (2016)
- Страницы: 341-348
- Раздел: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212403
- DOI: https://doi.org/10.1134/S1990478916030042
- ID: 212403
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
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.
Ключевые слова
Об авторах
V. Il’ev
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Автор, ответственный за переписку.
Email: iljev@mail.ru
Россия, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
S. Il’eva
Dostoevsky Omsk State University
Email: iljev@mail.ru
Россия, pr. Mira 55-A, Omsk, 644077
A. Navrotskaya
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Email: iljev@mail.ru
Россия, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
