Enviar artigo por via de e-mail Graph clustering with a constraint on cluster sizes
- Autores: Il’ev V.P.1,2, Il’eva S.D.2, Navrotskaya A.A.1,2
-
Afiliações:
- Sobolev Institute of Mathematics
- Dostoevsky Omsk State University
- Edição: Volume 10, Nº 3 (2016)
- Páginas: 341-348
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212403
- DOI: https://doi.org/10.1134/S1990478916030042
- ID: 212403
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
V. Il’ev
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Autor responsável pela correspondência
Email: iljev@mail.ru
Rússia, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
S. Il’eva
Dostoevsky Omsk State University
Email: iljev@mail.ru
Rússia, pr. Mira 55-A, Omsk, 644077
A. Navrotskaya
Sobolev Institute of Mathematics; Dostoevsky Omsk State University
Email: iljev@mail.ru
Rússia, pr. Akad. Koptyuga 4, Novosibirsk, 630090; pr. Mira 55-A, Omsk, 644077
Arquivos suplementares
